# Questions tagged [arithmetic-circuits]

The tag has no usage guidance.

87 questions
Filter by
Sorted by
Tagged with
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 ...
102 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}$?
39 views

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 ... 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 vote
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 ...
172 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?
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 ...
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)}$ [...
60 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 ...
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 ...
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 ...
189 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 ...
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 , Lemma 3 in , Decomposition Lemma in , also mentioned in ). My question is: Is ...
1 vote
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 ...
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$...
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
824 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 ...
1 vote
73 views

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 ...
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 ...
88 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...