The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
2answers
118 views

Complexity of smooth non-linear functions

EDIT: A more straightforward way of asking this question is: does evaluating a non-linear function require performing at least one multiplication? ORIGINAL QUESTION: I have an infinitely ...
0
votes
0answers
131 views

Greater-Than operator using an Arithmetic Circuit

How can I transform the term $x>C$ (i.e. the term assumes the value $1$ if $x>C$ and assumes the value $0$ otherwise) to an arithmetic circuit that computes it? Where $x$ is the input to the ...
6
votes
0answers
62 views

What are bounded-treewidth circuits good for?

One can talk of the treewidth of a Boolean circuit, defining it as the treewidth of the "moralized" graph on wires (vertices) obtained as follows: connect wires $a$ and $b$ whenever $b$ is the output ...
3
votes
1answer
134 views

Lower bounds for Polynomials computing the boolean functions

Expressing a boolean function $f$ $:\{ 0,1 \}^{n} \rightarrow \{0,1 \}$ using a polynomial $P(x_{1},...,x_{n})$, where $x_{1},...,x_{n}$ may be integer, finite fields, or other fields. One of the ...
6
votes
0answers
72 views

Practical algorithms for finding small arithmetic circuits

I have a multivariate integer polynomial $f : \mathbb{Z}^n \to \mathbb{Z}$ given as either as a circuit or as a list of monomials. I am interested in practical (though obviously exponential time) ...
12
votes
1answer
596 views

A course for learning algebraic complexity

I want to learn about algebraic algorithms and complexity thoery. In particular, I am interested in PIT. Is there a set of lecture notes, books, papers and surveys for students who have read standard ...
9
votes
1answer
135 views

Checking if a polynomial factors into linear factors

Let $f\in\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ be a polynomial given by an arithmetic circuit $C$ of size $s$. Given $C$ as the input, is there a deterministic algorithm to check whether all the ...
0
votes
0answers
30 views

arithmetic formula simplication

Consider a function $f : \mathbb R^m \rightarrow \mathbb R^n$. Function $f$ can be written down as a simple arithmetic program. It uses addition, subtraction, multiplication and division - however, ...
11
votes
0answers
209 views

Generalizations of the determinant/permanent problem?

A tantalizing open question in computational complexity is to understand the 'behavioral differences' between the determinant and the permanent. While the former is computable in polynomial time with ...
4
votes
1answer
156 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
60 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
144 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
162 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 ...
6
votes
0answers
207 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
132 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
123 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 ...
11
votes
2answers
466 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
81 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
397 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
168 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
149 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
233 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
97 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
145 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
778 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
351 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
222 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
162 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
129 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
123 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
715 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 ...