9 votes

Depth reduction for Boolean circuits

Unfortunately, the best known depth reductions for Boolean circuits only work for very restricted classes of circuits. Valiant (Valiant; Viola) proved that a circuit of size $O(n)$ and depth $O(\log{n}...
Alex Golovnev's user avatar
9 votes
Accepted

Are arithmetic circuits weaker than boolean?

The permanent would seem to qualify, at least conditionally (that is, assuming $\mathsf{VP}^0 \neq \mathsf{VNP}^0$). Note that the Boolean version of the permanent is just to decide whether a given ...
Joshua Grochow's user avatar
9 votes
Accepted

What are bounded-treewidth circuits good for?

We now understand that for any fixed bound $k \in \mathbb{N}$ on the treewidth, we can convert any Boolean circuit of treewidth less than $k$ to a so-called d-SDNNF circuit, in linear time and with ...
a3nm's user avatar
  • 9,269
9 votes
Accepted

VC dimension of polynomials over tropical semirings?

I've realized that the answer to my question is - yes: the VC dimension of degree $\leq d$ polynomials on $n$ variables over any tropical semiring is at most a constant times $n^2\log(n+d)$. This can ...
Stasys's user avatar
  • 6,765
6 votes

White-box sparse interpolation

There are deterministic algorithms that can do it even in time polynomial in $n$, $k$, $\log d$, and $L$ ($n$ numbers of variables, $k$ sparsity, and $d$ the degree, $L$ the bit length of the ...
Markus Bläser's user avatar
6 votes

White-box sparse interpolation

There are deterministic and randomized algorithm running in time $\mathrm{poly}(n,d,k)$, where $n$ is the number of variables, $d$ is the degree and $k$ is the sparsity. AFAIK, the results are stated ...
Ramprasad's user avatar
  • 2,482
5 votes
Accepted

Can a sum of polynomially many determinants be expressed as a single determinant of a poly-size matrix?

It is possible and proven in [1, Proposition 7]. More precisely, Malod and Portier show that the determinant is linearly closed, that is, every linear combination of the form $\sum_{i=1}^n \lambda_i ...
holf's user avatar
  • 2,174
4 votes

Reference request: Arithmetic circuit complexity

In addition to the references already mentioned, you could check out Xi Chen, Neeraj Kayal and Avi Wigderson (2011), Partial Derivatives in Arithmetic Complexity and Beyond, Foundations and Trends®...
Joshua Grochow's user avatar
4 votes

Reference request: Arithmetic circuit complexity

This depends on what you want to do. For more structural questions there is a relatively recent survey by Meena Mahajan: Meena Mahajan: Algebraic Complexity Classes. There is also the book by ...
smengel's user avatar
  • 156
4 votes
Accepted

Can reciprocal inputs speed up monotone computations?

I believe the answer to the Question 1 is negative. We introduce an auxiliary circuit type: $X_k$-circuits have inputs $x_1, \dots, x_n$ and $1/x_k,\dots,1/x_n$ and have in addition to $+$ and $\...
Vladimir Lysikov's user avatar
4 votes
Accepted

Lower bound for constant degree monotone arithmetic circuits

The Nisan--Wigderson polynomials are one example. That is, let $$ \mathrm{NW}_{n,m,d}(\vec{x}) := \sum_{\substack{p(t) \in \mathbb{F}_m[t] \\ \deg(p) \le d}} x_{1,p(1)} \cdots x_{n,p(n)}. $$ Let $k$ ...
Robert Andrews's user avatar
4 votes
Accepted

Low-depth arithmetic complexity of the product of $k$ matrices

I am not sure about specifically depth-three lower bounds, but there has been a lot of depth-4 (and 5) lower bounds, usually assuming other constraints as well. For instance (and without any claim of ...
Bruno's user avatar
  • 4,504
3 votes

What’s the complexity of this decision problem with bit shifting?

If I had to guess, I'd guess that the problem is hard, but I don't have a rigorous proof. I share below some musings on your problem, even though they don't lead to a clear answer to your question. ...
D.W.'s user avatar
  • 12.1k
3 votes

Can we do computing without electricity?

Short answer: yes, there are many "computers" which run without "electricity" (in the way most computers do nowadays). Read about Mechanical Computers, and more generally about ...
J..y B..y's user avatar
  • 2,776
3 votes
Accepted

In depth reduction of arithmetic formula why we get a $v$ st $\frac{s}3\leq |\Phi_v|\leq \frac{2s}{3}$

You do not cite the part of the survey that is actually relevant for getting the $s/3$ lower bound: Starting from the root, walk down to the leaves by always taking the child with a larger sub-tree ...
holf's user avatar
  • 2,174
3 votes

Reference request: Arithmetic circuit complexity

This is course on Arithmetic Circuit Complexity, offered by Prof Nitin Saxena (the S of AKS primality test). The syllabus and pre-requisites can be found here.
Gokul's user avatar
  • 131
3 votes

Reference request: Arithmetic circuit complexity

Another good source that I am surprised hasn't been mentioned yet is the survey by Ramprasad Saptharishi.
Abhishek Shetty's user avatar
3 votes

Adleman's theorem over infinite semirings?

This is only a partial answer to your general question (I'm not sure what a fully general formulation would be), but it suggests that working over sufficiently nice infinite semirings while ...
Andrew Morgan's user avatar
2 votes

Optimal evaluation of polynomials / rational functions

In Knuth Vol II Theorem E on page 494 he presents an algorithm that can evaluate a polynomial using $\frac{n}{2} + 2$ multiplications. The theoretical minimum is $\frac{n}{2}$, assuming generic ...
Remco Bloemen's user avatar
2 votes

Complexity of Polynomial Division

I don't know if this quite counts as an answer, but in fact this problem is equivalent to the matrix powering problem, so the references and comments on the question about matrix powering referenced ...
Joshua Grochow's user avatar
2 votes

Has there been a study of circuits operating on arrays?

Not really an answer, but would've been too long a comment. The result of Ben-Or and Cleve that arithmetic formulas can be simulated by branching programs of width 3, works over arbitrary non-...
Nikhil's user avatar
  • 1,354
2 votes

Arithmetic circuits over $GF(p)$ for computing $x \bmod 2$ given input $x \in GF(p)$

It's not clear if this is directly useful, but lower bounds are known for depth-3 circuits computing an $n$-variate version of your function over $\mathrm{GF}(p)$ for $p \neq 2$. See Theorem 3.7 in ...
Robert Andrews's user avatar
2 votes

How to build comparison operator (comparator) in an arithmetic circuit

I believe this is generally done in MPC by converting the sharing of the field element to some sharing more amenable to comparison. See this (section 6.3), or chapter 9 in Secure Multiparty ...
Mark Schultz-Wu's user avatar
1 vote
Accepted

doubt in the proof of reducing any arithmetic circuit to log(d) depth, where d is the degree of the polynomial it is computing

See that $w\in \mathcal{F}_m$ so $\deg(w)\geq m$ but $\deg(w_L),\deg(w_R)<m$. So if $\deg(w_L)=\deg(w_R)=m-1$ then $\deg(w)$ becomes $2m-2$. If $m$ is large enough then $2m-2 >m$. Hence we can ...
Soham Chatterjee's user avatar
1 vote
Accepted

Is homogeneity required in Hyafil's arithmetic circuit decomposition theorem when applied to monotone circuits?

No, homogeneity is not required when applying this theorem to monotone circuits, and in fact homogeneity is a quite technical restriction that can be removed even in the general case by weakening the ...
Laakeri's user avatar
  • 1,766
1 vote
Accepted

Evaluation of an arithmetic formula where the time depends on the length of the arguments of gates

EDIT: I was wrong about the implication to arithmetic circuits. I think it is possible. It uses ideas in parallel evaluation of arithmetic expressions and tree contraction. Consider the arithmetic ...
Chao Xu's user avatar
  • 4,439
1 vote

VNP is closed under taking coefficients using Valiant's criterion

Here is a related statement which can be proven "algebraically" (as opposed to going to the boolean world of #P/poly). Suppose $f(x_1,\ldots,x_n,y_1,\ldots,y_m) \in \text{VNP}$ for $m = \...
anamay's user avatar
  • 11

Only top scored, non community-wiki answers of a minimum length are eligible