16 votes
Accepted

Arithmetic circuits with just one threshold gate

The answer is “yes” if $t=n^{O(1)}$. More generally, a threshold $\{+,\cdot\}$-circuit of size $s$ with threshold $t$ can be simulated by a $\{\lor,\land\}$-circuit of size $O(t^2s)$. First, observe ...
15 votes
Accepted

Analogies between VNP and NP

The basic idea is that summing over all Boolean strings (VNP) is like counting the solutions to an NP problem. Even from this perspective, one sees that VNP is more like #P than NP. This is also true ...
15 votes
Accepted

Implications of Riemann Hypothesis variants in TCS

First, I’m not aware of any CS application of Riemann’s hypothesis as such. There are various applications of generalizations of RH. Second, a terminological note: contrary to popular belief, there ...
14 votes
Accepted

Why is HAMILTONIAN CYCLE so different from PERMANENT?

The following is a proof over any ring of characteristic zero that the Hamiltonian cycle polynomial is not a polynomial-size monotone projection of the permanent. The basic idea is that monotone ...
13 votes
Accepted

Straight line complexity of monomials

If $$f=(\Sigma_{i=1}^n x_i)^{2^n}$$ then it has ${2^n+n-1\choose n-1} \approx 2^{n^2}$ monomials and $L(f)=O(n)$. By a counting argument, there are $2^{O(n\log n)}$ straight-line programs of length $O(...
  • 13.7k
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 ...
  • 6,635
9 votes
Accepted

Matrix vector multiplication algorithm using minimal number of additions

This is essentially the problem that motivated Valiant to introduce matrix rigidity into complexity (as far as I understand the history). A linear circuit is an algebraic circuit whose only gates ...
9 votes

Integer multiplication when one integer is fixed

I am not sure whether this is directly relevant to the question, but the following elementary result might be of interest. Given a fixed natural number $k$, the operation $n \to kn$ can be realized by ...
  • 4,721
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 ...
  • 7,485
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 ...
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}...
8 votes

Lower bounds for noncommutative arithmetic circuits with exact division?

To my knowledge, such a reduction is in fact known: Hrubes and Wigderson ITCS 2014 show how division gates can be eliminated from non-commutative circuits and formulas which compute polynomials. They ...
8 votes

Straight line complexity of monomials

Note: This is an expansion of a previous comment, since the OP explicitely asked for weaker upper bounds. The total degree of polynomial $f$ is bounded by $2^{L(f)}$ since each operation can at most ...
  • 4,400
8 votes
Accepted

Randomized identity-testing for high degree polynomials?

It’s not exactly clear to me what is the input of the problem and how do you enforce the restriction $p=2^{\Omega(n)}$, however, under any reasonable formulation the answer is no for multivariate ...
7 votes
Accepted

Any polynomial which is hard to count but easy to decide?

(I am posting my comments as an answer in response to the OP’s request.) As for Question 1, let fn: {0,1}n→ℕ be a family of functions whose arithmetic circuit requires exponential size. Then so does ...
  • 16.3k
7 votes
Accepted

Complexity of smooth non-linear functions

Note that proving that evaluation of $f$ takes at least as much time as integer multiplication only shows that it needs time $\Omega(M(n))$; while this is generally assumed to be at least $n\log n$, ...
7 votes

Implications of Riemann Hypothesis variants in TCS

Assuming an extended Riemann Hypothesis, L. M. Adleman and H. W. Lenstra gave a polynomial time algorithm to find an irreducible polynomial of a desired degree over a finite field: http://www.math....
7 votes

Matrix vector multiplication algorithm using minimal number of additions

If you do not allow subtraction, then you are in the semi-group/monotone setting and there are tight lower bounds known for many natural matrices $M$ that come from computational geometry. (The ...
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 ...
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 ...
  • 2,447
6 votes

Monotone arithmetic circuit complexity of elementary symmetric polynomials?

One challenge is that if you remove the "monotone" restriction, we do know how to compute such things efficiently. You can compute the value of all $S_0^n,\dots,S_n^n$ (evaluate all $n+1$ elementary ...
  • 10.5k
5 votes

Complexity of smooth non-linear functions

First, super-linear lower bounds on multiplying two integers are not known: for all we know, there may be an $O(n)$-time algorithm for multiplying two $n$-bit integers. So even if your "proof by ...
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®...
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 ...
  • 146
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 ...
  • 4,400
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 $\...
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 ...
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.
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.
  • 131
2 votes

How quickly can we decompose a number into a set of residues?

If $m=2^k-t$ where $t$ is small, then you can reduce modulo $m$ faster. In particular, $a \cdot 2^k + b \equiv at+b \pmod{m}$, so reducing an $\alpha k$-bit number modulo $m$ typically requires $\...
  • 10.5k

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