# Tag Info

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 ...
• 14.9k
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 ...
• 35.9k
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.9k
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 ...
• 35.9k
Accepted

• 2,153

### 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 ...
• 1,899

### 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
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 ...
• 14.9k
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
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$, ...
• 14.9k

### 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....

### 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 ...

### 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 ...
• 2,828

### 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

### 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

### 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 ...
• 35.9k

### 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®...
• 35.9k

### 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
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
Accepted

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 ... • 1,419 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