The arithmetic-circuits tag has no wiki summary.
-1
votes
0answers
21 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
209 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
78 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
122 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 ...
17
votes
2answers
488 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
302 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
170 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
129 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
105 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
574 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 ...
