# Questions tagged [arithmetic-circuits]

The tag has no usage guidance.

85 questions
Filter by
Sorted by
Tagged with
199 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 ...
• 96
121 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}$?
• 901
125 views

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 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 0 answers 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 ... • 1,598 0 votes 1 answer 328 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 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 ... 4 votes 0 answers 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)} $[... 0 votes 0 answers 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 ... 5 votes 1 answer 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 ... 0 votes 0 answers 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 ... • 13k 8 votes 0 answers 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 ... • 37.4k 3 votes 1 answer 118 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,786 1 vote 0 answers 86 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 141 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$... • 13k 3 votes 1 answer 194 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 946 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 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{~...
• 13k
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 ...