The tag has no wiki summary.

learn more… | top users | synonyms

4
votes
1answer
148 views

Can a polynomial sized arithmetic ciruits perform integer division?

Can we perform integer division with a polynomial size arithmetic circuit over $\mathbb{Q}$ that takes as input the numerator and denominator?
4
votes
0answers
52 views

Complexity of equivalence testing of arithmetic circuits

I have a very specific problem that appears to be close to equivalence testing for arithmetic circuits (checking whether the computed functions are the same). Since I'm completely new to the field, ...
6
votes
1answer
128 views

arithmetic circuits for polynomials (updated)

I am concerned about the following question, consider $P_n(x)= \sum_{i=0}^n \frac{x^n}{n!}$ Is there a straight line program (or arithmetic circuits) of polynomial size (wrt $n$) for the polynomial ...
6
votes
1answer
145 views

Uniformity vs. nonuniformity in algebraic complexity theory

I understand that the study of Boolean circuits and nonuniform complexity classes was introduced to (hopefully) prove separation of uniform complexity classes. In this sense, nonuniform computational ...
5
votes
0answers
145 views

Complexity of Polynomial Division

Let $P(x)$ be a univariate polynomial with integer coefficients where both coefficients and degrees are in binary and let $q(x)$ be another polynomial also with integer coefficients where the degrees ...
5
votes
1answer
113 views

Degree restriction for polynomials in $\mathsf{VP}$

why do we need the restriction on the degree for a polynomial to be in VP due to which $(\prod_{i=0}^{n} x_i)^{2^n}$ $\notin$ VP even though it has a poly-size circuit?
2
votes
1answer
103 views

VNP completeness of Permanent

Can some one suggest a good source for VNP completeness of Permanent. I tried reading it from book on Algebraic complexity theory by Burgisser,clausen,shokrollahi,lickteig. And What is the best known ...
10
votes
2answers
409 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 ...
4
votes
0answers
80 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?
9
votes
2answers
385 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
156 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 ...
-3
votes
1answer
147 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
227 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
92 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 ...
8
votes
1answer
144 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 ...
19
votes
2answers
717 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
342 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
210 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
158 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
126 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
120 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 ...
20
votes
5answers
689 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 ...