The arithmetic-circuits tag has no wiki summary.
10
votes
2answers
193 views
Determinants and Matrix Multiplication - Similarity and differences in algorithmic complexity and arithmetic circuit size
I am trying to understand the relation between algorithmic complexity and circuit complexity of Determinants and Matrix Multiplication.
It is known that the determinant of an $n\times n$ matrix can ...
3
votes
0answers
64 views
Size depth tradeoffs for monotone arithmetic circuits
Are there any size depth trade-offs known for monotone arithmetic circuits that compute permanent and determinant?
7
votes
2answers
307 views
Cancellation and determinant
Berkowitz algorithm provides a polynomial size circuit with logarithmic depth for determinant of a square matrix using matrix powers. The algorithm implicitly uses cancellation. Is cancellation ...
8
votes
0answers
128 views
Grigoriev-Karpinski for the permanent
Grigoriev and Karpinski (ps.Z) showed that any depth-3 circuit over a fixed finite field computing $\mathrm{Det}_n$ requires $2^{\Omega(n)}$ size. I had the misconception(?) until recently that the ...
-2
votes
1answer
107 views
computing with gates on polar coordinates, functionally complete wrt boolean functions?
this question is inspired by a particular somewhat "natural" physical system specifically constructed to mimic another complex highly-studied physical computing system. (some may astutely guess at ...
7
votes
2answers
213 views
How efficiently can circuits over sets of naturals be transformed to boolean circuits?
I am interested in reducing a circuit over sets of naturals (see here for some basic notions about this type of circuits) to a boolean circuit computing the same output. A very basic circuit of this ...
1
vote
0answers
83 views
Satisfiability of circuits with infinite input
As we all know, satisfiability of Boolean circuits is NP-complete.
I am wondering if there are any studies of circuits with infinite inputs?
That is, suppose the input is from the set ...
7
votes
1answer
130 views
Is there an alternate proof or an exposition of: Exponential lower bound for $\Sigma\Pi\Sigma$ circuits [Grigoriev-Karpinski(1998)]?
Is there an alternate proof or an exposition of the result of Grigoriev and Karpinski (STOC 1998, doi:10.1145/276698.276872) on the exponential lower bounds for Depth 3 arithmetic circuits computing ...
18
votes
2answers
521 views
Lower bound for determinant and permanent
In light of the recent chasm at depth-3 result (which among other things yields a $2^{\sqrt{n}\log{n}}$ depth-3 arithmetic circuit for the $n \times n $ determinant over $\mathbb{C}$), I have the ...
11
votes
3answers
309 views
Arithmetic circuits with $\min$, $\max$, and average over $[0,1]$
Consider a circuit that takes as inputs numbers in $[0,1]$, and has gates that consist of the functions $\max(x, y)$, $\min(x, y)$, $1 - x$, and $\frac{x+y}{2}$.
The output of the circuit is then also ...
10
votes
1answer
177 views
Why lower bounds for boolean Circuits does not imply arithmetic circuits lower bounds
My question is why lower bounds for depth 3 Boolean circuits with gates "and" and "xor" for determinant does not imply the same lower bounds for arithmetic circuits over $\mathbb{Z}$?
What is wrong ...
4
votes
1answer
131 views
Computing every boolean function with a polynomial over $\mathbb{F}_3$?
The following paper briefly mentions the power of $MOD_6$ gates (page 3), and relies on the unstated fact that every boolean function can be computed with an arithmetic circuit of depth 2 over ...
2
votes
0answers
112 views
Expressive power of (versions of) weighted average
Consider the arithmetic expressions obtained by allowing the constants 0 and 1, boolean variables, and allowing the operations $\min\{s,t\},\max\{s,t\}$, and $1-t$ where $s,t$ are expressions.
Clearly ...
7
votes
0answers
108 views
Computing the Fourier-Walsh coefficients of an arithmetic circuit
Given an $f$-fan in arithmetic circuit of depth $d$ over $GF(q)$ (for some prime $q$) and the set of variables $(x_1,\ldots,x_n)$, what is the state of the art upper bound for calculating the ...
19
votes
5answers
597 views
Monotone arithmetic circuits
The state of our knowledge about general arithmetic circuits seems to be similar to the state of our knowledge about Boolean circuits, i.e. we don't have good lower-bounds. On the other hand we have ...
