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}...
- 2,247
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,685
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 ...
- 36.9k
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 ...
- 8,896
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 ...
- 36.9k
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 ...
- 1,899
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 ...
- 18.1k
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 ...
- 2,878
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,482
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 ...
- 11.7k
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 ...
- 2,164
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,439
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®...
- 36.9k
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 ...
- 156
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$ ...
- 743
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 $\...
- 632
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 ...
- 2,733
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 ...
- 2,164
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
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.
- 148
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,429
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.
...
- 11.7k
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 ...
- 36.9k
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 $\...
- 11.7k
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-...
- 1,344
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 ...
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 ...
- 743
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 ...
- 918
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 ...
- 288
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 ...
- 1,767
Only top scored, non community-wiki answers of a minimum length are eligible