# Questions tagged [arithmetic-circuits]

The tag has no usage guidance.

85 questions
Filter by
Sorted by
Tagged with
391 views

102 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 ...
1 vote
114 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 ...
326 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?
81 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 ...
78 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)}$ [...
67 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 ...
146 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 ...
94 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 ...
201 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 ...
1k 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 ...
1k 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 ...
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 ...
274 views

434 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 ...
238 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 ...
1 vote
257 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 ...
117 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 ...
355 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 ...
90 views

165 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 ...
307 views

### Machine characterization of $SAC^i$

$SAC^i$ is the class of decision problems solvable by a family of $O({\log}^i{n})$ depth circuits with unbounded-fanin OR and bounded-fanin AND gates. Negations are only allowed at the input level. It ...
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 ...
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 ...