Questions tagged [arithmetic-circuits]
The arithmetic-circuits tag has no usage guidance.
87
questions
3
votes
1
answer
169
views
What’s the complexity of this decision problem with bit shifting?
I’ve been wondering about the computational complexity of a problem that involves bit shifting.
Let me define some notation before I present the problem.
If $\langle{b}\rangle$ is a bitstring ...
4
votes
1
answer
105
views
Lower bound for constant degree monotone arithmetic circuits
Do we know an explicit constant degree polynomial that requires monotone arithmetic circuits of size $n^{10}$?
- 891
0
votes
0
answers
40
views
Why $Rank(C)< R(k,d)$ for Depth 3 Balckbox PIT Algorithm implies $C$ is zero
I was reading the Survey on Polynomial Identity Testing by Nitin Saxena. In the Depth 3 Blackbox PIT Algorithm he first finds $O(k^2d^2+2^k)$ many subspaces of the linear forms of the $\sum\prod\sum(...
- 288
2
votes
1
answer
115
views
doubt in the proof of reducing any arithmetic circuit to log(d) depth, where d is the degree of the polynomial it is computing
In the survey see section 5.3.2 : Depth reduction for arithmetic circuits for notations.
I follow the proof of the following two identities :
$[u]=\Sigma_{w\in \cal{F}_m}[u:w].[w]$ where $deg(u)\geq ...
- 123
3
votes
0
answers
99
views
Complexity of checking if a given prime number can be computed using at most $s$ addition/multiplication operations?
Given are a prime number $p$ and a parameter $s\in\mathbb{N}$.
What is the computational complexity of the problem of determining whether $p$ is computable by a series of at most $s$ steps, each being ...
user67795
0
votes
0
answers
102
views
Quantum END OF THE LINE Representation?
The complexity class PPAD is heavily based on the problem END OF THE LINE. However, it is unclear how to represent this problem on a quantum computer; i.e. the graph representation of having two ...
- 1
1
vote
0
answers
106
views
Boolean formula complexity of arithmetic expressions
This is a followup question to this other question, where I was told that multiplication is in $NC^1$ so can be computed with a circuit of polynomial size and logarithmic depth, hence also with a ...
- 1,588
0
votes
1
answer
177
views
Can we do computing without electricity?
If electricity was never discovered, could we still make funcional computers to perform some level of useful tasks?
Or won't we be able to build anything comparable in terms of computer power?
- 101
0
votes
1
answer
75
views
In depth reduction of arithmetic formula why we get a $v$ st $\frac{s}3\leq |\Phi_v|\leq \frac{2s}{3}$
I am reading Depth Reduction of Arithmetic Formula form the survey of Ramprasad Saptharishi. Now in the proof of depth reduction due to Brent, 74 that
Let $f$ be an n-variate degree d polynomial ...
- 288
4
votes
0
answers
76
views
How to learn the intuition behind probabilistic arguments in Algebraic Complexity lower bounds
I was reading the lower bounds of arithmetic circuits. There in the proof of the theorem
Over field $\mathbb{F}_q$, determinant, permanent requires depth-3 circuits of size $2^{\Omega(n)} $ [...
- 288
0
votes
0
answers
62
views
Any arithmetic circuit of size $s$ and depth $\Delta$ can be converted to a formula of size $s' \leq s^{\Delta}$
I was reading Ramprasad Saptharishi's survey on Arithmetic Circuits.
There in section 2.1.1 fact 2.3 it has
Any arithmetic circuit of of depth $\Delta$ and size $s$, can be
simulated by an arithmetic ...
- 288
5
votes
1
answer
143
views
Can a sum of polynomially many determinants be expressed as a single determinant of a poly-size matrix?
(copied from a mathoverflow question because I realized this may be more appropriate for it) Let $A_1,A_2,...,A_k$ be $N$-by-$N$ matrices, with indeterminate entries in some field (say real or complex ...
- 225
0
votes
0
answers
91
views
Boolean vs algebraic circuits difference
Valiant, Skyum, Berkowitz and Rackoff in https://epubs.siam.org/doi/10.1137/0212043 showed that $VP=VNC^2$, namely, that arithmetic circuits can be parallelized.
What is the central reason such a ...
- 12.8k
8
votes
0
answers
190
views
"Addition function" that works for both perm and det simultaneously?
For $f = (f_n)$ a family of polynomials where $f_n$ is a polynomial in $n^2$ variables (which we can think of as the entries of an $n \times n$ matrix), say a function $S(A,B)$ is an addition function ...
- 36.9k
3
votes
1
answer
108
views
Is homogeneity required in Hyafil's arithmetic circuit decomposition theorem when applied to monotone circuits?
I'm new to circuit complexity, and trying to understand Hyafil's decomposition theorem (Theorem 1 in [1], Lemma 3 in [2], Decomposition Lemma in [3], also mentioned in [4]). My question is: Is ...
- 1,767
1
vote
0
answers
84
views
Multiplicative-depth 1 composition of arithmetic circuits
I am trying to find information about the following problem. Let $C_1$ and $C_2$ be any two poly-size arithmetic circuits on input vectors x₁ and x₂ correspondingly. Assume that a third arithmetic ...
- 401
2
votes
0
answers
136
views
Matrix multiplication when one matrix is fixed
Let $A$ be a fixed positive entried integer matrix of size $a\times n$ with $\ell$ bits per entry
One is allowed to pre-process this matrix as appropriate.
Given another positive integer entried $B$...
- 12.8k
3
votes
1
answer
188
views
Arithmetic circuits over $GF(p)$ for computing $x \bmod 2$ given input $x \in GF(p)$
Let $p$ be a prime. Suppose we consider the function $f: GF\left(p \right) \rightarrow \left\{0, 1 \right\}$ where $f(x) = x \bmod 2$ for all.
The question is the following: are there any known ...
1
vote
1
answer
832
views
How to build comparison operator (comparator) in an arithmetic circuit
I am trying to convert a basic program into an arithmetic circuit. I am stuck on the step of converting the greater than operator into an arithmetic circuit. To be specific, I do not know how to ...
- 19
1
vote
0
answers
73
views
Straight line programs with $\sqrt{~}$
A straight line program with division is very powerful https://rjlipton.wordpress.com/2012/10/16/one-mans-floor-is-another-mans-ceiling/.
Is it possible to reduce a straight line program with $\sqrt{~...
- 12.8k
9
votes
1
answer
399
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 ...
- 91
7
votes
1
answer
362
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,\...
- 6,685
5
votes
1
answer
237
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 ...
- 4,367
3
votes
0
answers
114
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 ...
- 31
3
votes
0
answers
88
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)\...
- 596
2
votes
0
answers
53
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 ...
- 891
7
votes
4
answers
441
views
Reference request: Arithmetic circuit complexity
I am completely new to this field. I want to read the prelims and unfortunately, I don't see any book written for a beginner in this area. Can anyone give me some basic starting points/references(text/...
- 171
6
votes
1
answer
258
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,...
- 161
3
votes
0
answers
168
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 ...
- 891
7
votes
2
answers
150
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 ...
- 4,439
1
vote
0
answers
107
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$ ...
- 1,443
6
votes
1
answer
243
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 ...
- 173
3
votes
0
answers
105
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 ...
- 12.8k
14
votes
1
answer
803
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 ...
- 6,685
13
votes
1
answer
422
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 ...
- 6,685
10
votes
0
answers
160
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,...
- 1,345
5
votes
0
answers
407
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,443
1
vote
1
answer
238
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 ...
- 419
2
votes
1
answer
115
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 $\...
- 891
0
votes
0
answers
123
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 ...
user34945
12
votes
1
answer
578
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}\,,
$$
...
- 6,685
7
votes
1
answer
162
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 ...
- 891
14
votes
1
answer
1k
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 ...
- 6,685
5
votes
1
answer
98
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 ...
- 2,100
10
votes
2
answers
302
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 ...
- 11k
4
votes
1
answer
450
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 ...
- 11k
9
votes
2
answers
880
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 ...
- 11k
11
votes
2
answers
299
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 ...
- 727
25
votes
1
answer
1k
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 ...
- 6,685
1
vote
0
answers
410
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 ...
- 11k