Questions tagged [arithmetic-circuits]
The arithmetic-circuits tag has no usage guidance.
8
votes
1answer
191 views
Depth reduction for Boolean circuits
This result by Tavenas, Koiran and others show that any polynomial computed by a circuit of size $s$ is computed by a depth-4 homogenous circuit of size $s^{\sqrt{d}}$.
Are there any similar results ...
6
votes
0answers
138 views
Can reciprocal inputs speed up monotone computations?
A $(+,\times,1/x_i)$ circuit is a standard monotone arithmetic $(+,\times)$ circuit with the only difference that now besides the input variables $x_1,\ldots,x_n$, also their reciprocals $1/x_1,\...
5
votes
1answer
226 views
Evaluation of an arithmetic formula where the time depends on the length of the arguments of gates
Let $(X,+,\cdot)$ be a commutative ring. Let $|\cdot|\colon X\to \mathbb{N}$ be a function that satisfies $|x+y|\leq |x|+|y|$ and $|xy|\leq |x|+|y|$. We call the function length, and length is always ...
3
votes
0answers
88 views
Why do most 0/1 matrices need linear arithmetic circuits of size $\Omega(n^2/\log(n))$?
I am reading Alon et al.'s paper Linear Circuits over $GF(2)$ and I am having trouble seeing the counting argument showing that most matrices need a circuit of size $\Omega(n^2/\log n)$. This result ...
3
votes
0answers
75 views
How many arithmetic and max operations does it take to compute Dynnikov's action of the braid groups on $\mathbb{Z}^{2n}$?
A function $f:X^{2}\rightarrow X^{2}$ is said to satisfy the Yang-Baxter equation if
$$(f\times\textrm{Id}_{X})\circ(\textrm{Id}_{X}\times f)\circ(f\times\textrm{Id}_{X})=(\textrm{Id}_{X}\times f)\...
2
votes
0answers
42 views
Arithmetic circuits with restrictions on occurrence of pairs of variables
I am curious if the following model was studied or has some obvious lower bounds:
We want to compute a polynomial $P(x_1,x_2, \dots , x_n)$. Suppose we have a graph G on $n$ nodes that we are going ...
6
votes
0answers
141 views
VNP is closed under taking coefficients using Valiant's criterion
We consider the family of polynomials
$$\{f_n(x_1,\dots,x_n,y_1,\dots,y_n)\}\in\mathsf{VNP}$$
We want to show that the family
$$\{h_n(x_1,\dots,x_n)\}$$
is in $\mathsf{VNP}$. Where $h_n(x_1,\dots,...
3
votes
0answers
161 views
Circuit's with gate computing only “simple” functions
I was curious if something like that is known or was studied.
Let's call a function simple if it is computable by $AC_0$ circuit of depth $\leq d$ and size $\leq n^k$ for fixed $k,d$.
Now let's ...
6
votes
2answers
128 views
White-box sparse interpolation
Let $C$ be an arithmetic circuit that represents a polynomial $f\in\mathbb K[x_1,\dotsc,x_n]$, with the promise that $f$ has at most $k$ nonzero terms. What is (known about) the complexity of ...
1
vote
0answers
75 views
Tribes function vs (modified) polynomial threshold circuits
Are there lowerbounds known for representing the Tribes function by a circuit consisting of a single layer of polynomial threshold gates feeding into maybe a trivial summing gate? (Even for degree $1$ ...
7
votes
1answer
220 views
Has there been a study of circuits operating on arrays?
Much ink has been spilled studying the theory surrounding computation by combinatorial circuits operating on bits or boolean values - with AND, OR and NOT gates (as those are enough to implement any ...
3
votes
0answers
103 views
Fixed parameter Integer Programming circuit depth complexity
It is well known Lenstra's and Kannan's algorithm achieves $n$-variable parameter $L$-bit integer programming solvability in $O(n^nL)$ time and $O(L)$ space.
If implemented as an arithmetic circuit ...
15
votes
1answer
466 views
VC dimension of polynomials over tropical semirings?
As in this question, I am interested the $\mathbf{BPP}$ vs. $\mathbf{P}$/$\mathrm{poly}$ problem for tropical $(\max,+)$ and $(\min,+)$ circuits. This question reduces to showing upper bounds for the ...
13
votes
1answer
297 views
Adleman's theorem over infinite semirings?
Adleman has shown in 1978 that $\mathrm{BPP}\subseteq \mathrm{P/poly}$: if a boolean function $f$ of $n$ variables can be computed by a probabilistic boolean circuit of size $M$, then $f$ can be also ...
11
votes
0answers
151 views
Checking a long product of matrices
Given a set of n-by-n integer matrices $\{A_1, \dots, A_m\}$, for a word $w=w_1 w_2\cdots w_l$ over $\{1, \dots, m\}$, we define $A_w:=A_{w_1}\cdots A_{w_l}$.
The question is to decide, given $\{A_1,...
5
votes
0answers
344 views
About the ``recent" paper by Razborov in the Annals of Mathematics
Recently this paper on complexity theory was published at the Annals of Mathematics by Razborov, http://annals.math.princeton.edu/2015/181-2/p01. Curiously this seems to have been submitted to the ...
1
vote
1answer
91 views
Optimal evaluation of polynomials / rational functions
A common way to compute the value a polynomial is to write it in Horner form. However, this isn't always the fastest way to evaluate it. Setting aside concerns of numerical precision, take the ...
3
votes
1answer
90 views
Low-depth arithmetic complexity of the product of $k$ matrices
Is anything known about the size of $\Sigma\Pi\Sigma$ (or other constant depth) circuits for the product of $k$ matrices?
Trivial upper bounds (up to small factors) are:
if $k=2$, then there are $\...
0
votes
0answers
114 views
Arithmetic complexity of matrix powering with non-commutative entries
Assume $M\in\Bbb Z_{\geq0}[x_1,\dots,x_n]^{m\times m}$ be an $m\times m$ matrix in $n$ variables with $x_i$ being non-commutative.
What is the complexity class and circuit and formula complexity of ...
13
votes
1answer
468 views
Are arithmetic circuits weaker than boolean?
Let $A(f)$ denote the minimum size of a (non-monotone) arithmetic $(+,\times,-)$ circuit
computing a given multilinear polynomial
$$
f(x_1,\ldots,x_n)=\sum_{e\in E}c_e\prod_{i=1}^n x_i^{e_i}\,,
$$
...
8
votes
1answer
123 views
Lower bounds for noncommutative arithmetic circuits with exact division?
It is known that for general arithmetic circuits there is not much of a difference between standard model and one with division: any circuit with divisions that computes a polynomial can be simulated ...
15
votes
1answer
651 views
Monotone arithmetic circuit complexity of elementary symmetric polynomials?
The $k$-th elementary symmetric polynomial $S_k^n(x_1,\ldots,x_n)$ is the sum of all $\binom{n}{k}$ products of $k$ distinct variables.
I am interested in the monotone arithmetic $(+,\times)$ circuit ...
5
votes
1answer
92 views
How quickly can we decompose a number into a set of residues?
Basically, if we are given a natural $x$, in binary, with $x < m_0 \cdot m_1 \cdot m_2 \cdot \dots \cdot m_n$, how quickly can we find $x \bmod m_0$, $x \bmod m_1$,..., and $x \bmod m_n$? In other ...
10
votes
2answers
238 views
Matrix vector multiplication algorithm using minimal number of additions
Consider the following problem:
Given a matrix $M$
we want to optimize the number of additions in
the multiplication algorithm for computing $v \mapsto Mv$.
I find this problem interesting ...
4
votes
1answer
350 views
Analogies between VNP and NP
Valiant introduced the class VNP with respect to "arithmetic circuits" over 35 years ago in a "rough" analogy to NP. Recently, there have been major advances in the area of arithmetic circuits eg as ...
8
votes
2answers
759 views
Implications of Riemann Hypothesis variants in TCS
The over ~1½ century old Riemann Hypothesis has deep implications in mathematics and a large edifice of math theory is now proved conditionally on it and numerous variants. I recently came across a ...
11
votes
2answers
240 views
Straight line complexity of monomials
Let $k$ be some field. As usual, for an $f\in k[x_{1},x_{2},\ldots,x_{n}]$
we define $L(f)$ to be the straight-line complexity of $f$ over
$k$. Let $F$ be the set of monomials of $f$, namely the ...
23
votes
1answer
817 views
Why is HAMILTONIAN CYCLE so different from PERMANENT?
A polynomial $f(x_1,\ldots,x_n)$ is a monotone projection of a
polynomial $g(y_1,\ldots,y_m)$ if $m$ = poly$(n)$, and there is an assignment
$\pi:\{y_1,\ldots,y_m\}\to\{x_1,\ldots,x_n, 0,1\}$ such ...
1
vote
0answers
250 views
intuition that VP=?VNP is (not?) connected to P=?NP
recently there has been major progress into the VP=?VNP problem for algebraic circuits originated by Valiant, inspiring some optimistic outlook on its eventual or imminent resolution.[1]
what is an ...
21
votes
1answer
486 views
Arithmetic circuits with just one threshold gate
When restricted to $0$-$1$ inputs, every $\{+,\times\}$-circuit $F(x_1,\ldots,x_n)$ computes some
function $F:\{0,1\}^n\to \mathbb{N}$. To obtain a boolean function, we can just add
one fanin-1 ...
15
votes
1answer
484 views
Any polynomial which is hard to count but easy to decide?
Every monotone arithmetic circuit, i.e. a $\{+,\times\}$-circuit, computes some multivariate
polynomial $F(x_1,\ldots,x_n)$ with nonnegative integer coefficients. Given a polynomial
$f(x_1,\ldots,x_n)$...
9
votes
1answer
185 views
Randomized identity-testing for high degree polynomials?
Let $f$ be an $n$-variate polynomial given as an arithmetic circuit of size poly$(n)$, and let $p = 2^{\Omega(n)}$ be a prime.
Can you test if $f$ is identically zero over $\mathbb{Z}_p$, with time ...
2
votes
2answers
165 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
171 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 ...
13
votes
1answer
220 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 ...
5
votes
1answer
459 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
97 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) ...
14
votes
1answer
1k 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
186 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
58 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
276 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 ...
5
votes
1answer
185 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
92 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
184 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 ...
7
votes
1answer
313 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 ...
8
votes
0answers
591 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
290 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
274 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
1k 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
99 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?
