Questions tagged [arithmetic-circuits]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 ...
Sophie Weigle's user avatar
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}$?
ivmihajlin's user avatar
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(...
Soham Chatterjee's user avatar
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 ...
emmy's user avatar
  • 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 ...
user avatar
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 ...
Steven's user avatar
  • 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 ...
Nicola Gigante's user avatar
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?
Joe DiNottra's user avatar
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 ...
Soham Chatterjee's user avatar
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)} $ [...
Soham Chatterjee's user avatar
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 ...
Soham Chatterjee's user avatar
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 ...
Matt Hastings's user avatar
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 ...
Turbo's user avatar
  • 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 ...
Joshua Grochow's user avatar
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 ...
Laakeri's user avatar
  • 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 ...
cryptocat's user avatar
  • 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$...
Turbo's user avatar
  • 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 ...
A Lost Cryptographer's user avatar
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 ...
user53169's user avatar
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{~...
Turbo's user avatar
  • 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 ...
Math Learner's user avatar
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,\...
Stasys's user avatar
  • 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 ...
Chao Xu's user avatar
  • 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 ...
ralphS16's user avatar
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)\...
Joseph Van Name's user avatar
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 ...
ivmihajlin's user avatar
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/...
ViX28's user avatar
  • 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,...
user554578's user avatar
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 ...
ivmihajlin's user avatar
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 ...
Bruno's user avatar
  • 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$ ...
gradstudent's user avatar
  • 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 ...
einpoklum's user avatar
  • 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 ...
Turbo's user avatar
  • 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 ...
Stasys's user avatar
  • 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 ...
Stasys's user avatar
  • 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,...
maomao's user avatar
  • 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 ...
gradstudent's user avatar
  • 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 ...
Arthur B's user avatar
  • 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 $\...
ivmihajlin's user avatar
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 ...
user avatar
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}\,, $$ ...
Stasys's user avatar
  • 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 ...
ivmihajlin's user avatar
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 ...
Stasys's user avatar
  • 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 ...
Matt Groff's user avatar
  • 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 ...
vzn's user avatar
  • 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 ...
vzn's user avatar
  • 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 ...
vzn's user avatar
  • 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 ...
Gorav Jindal's user avatar
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 ...
Stasys's user avatar
  • 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 ...
vzn's user avatar
  • 11k