Highest voted questions tagged arithmetic-circuits - Theoretical Computer Science Stack Exchange most recent 30 from cstheory.stackexchange.com 2022-01-20T20:03:39Z https://cstheory.stackexchange.com/feeds/tag?tagnames=arithmetic-circuits&sort=votes https://creativecommons.org/licenses/by-sa/4.0/rdf https://cstheory.stackexchange.com/q/2517 36 Integer multiplication when one integer is fixed Turbo https://cstheory.stackexchange.com/users/1812 2010-10-28T06:34:05Z 2021-01-26T05:40:09Z <p><span class="math-container">$n$</span> is a parameter in the problem.</p> <p>For every <span class="math-container">$n$</span> we pick a random integer <span class="math-container">$a_n\in\{2^{n-1},2^{n-1}+1,\dots,2^n-1\}$</span> where <span class="math-container">$n\in\{1,2,\dots\}$</span>.</p> <p><strong>Problem</strong>: Given <span class="math-container">$n$</span> what is the complexity of multiplication function <span class="math-container">$f_n(x)=a_nx$</span> where <span class="math-container">$x\in\{0,1,\dots,2^n-1\}$</span>?</p> <p>One is allowed to pre-process integers <span class="math-container">$a_n$</span> as appropriate.</p> <p><strong>Upper Bound:</strong> We already have <span class="math-container">$n^{1+\epsilon}$</span> complexity algorithms by <span class="math-container">$\mathsf{FFT}$</span> and Karatsuba.</p> <p>The query here is whether <span class="math-container">$\epsilon=0$</span> by anything cleverer?</p> <p><strong>Conjecture:</strong> <span class="math-container">$\exists c&gt;0,n_0&gt;0$</span> such that at every <span class="math-container">$n\in\mathbb Z_{&gt;n_0}$</span> the number of constants <span class="math-container">$a_n$</span> where <span class="math-container">$\epsilon=0$</span> is supported is <span class="math-container">$&gt;2^{cn}$</span>.</p> https://cstheory.stackexchange.com/q/27496 25 Why is HAMILTONIAN CYCLE so different from PERMANENT? Stasys https://cstheory.stackexchange.com/users/5788 2014-11-18T18:02:27Z 2021-12-16T10:11:01Z <p>A polynomial <span class="math-container">$f(x_1,\ldots,x_n)$</span> is a <i>monotone projection</i> of a polynomial <span class="math-container">$g(y_1,\ldots,y_m)$</span> if <span class="math-container">$m$</span> = poly<span class="math-container">$(n)$</span>, and there is an assignment <span class="math-container">$\pi:\{y_1,\ldots,y_m\}\to\{x_1,\ldots,x_n, 0,1\}$</span> such that <span class="math-container">$f(x_1,\ldots,x_n)=g(\pi(y_1),\ldots,\pi(y_m))$</span>. That is, it is possible to replace each variable <span class="math-container">$y_j$</span> of <span class="math-container">$g$</span> by a variable <span class="math-container">$x_i$</span> or a constant <span class="math-container">$0$</span> or <span class="math-container">$1$</span> so that the resulting polynomial coincides with <span class="math-container">$f$</span>.</p> <p> I am interested in (the reasons for) the difference between the permanent polynomial PER and the Hamiltonian cycle polynomial HAM: <span class="math-container">$$\mbox{PER}_n(x)=\sum_{h}\prod_{i=1}^{n}x_{i,h(i)}\ \ \ \ \mbox{and} \ \ \ \ \mbox{HAM}_n(x)=\sum_{h}\prod_{i=1}^{n}x_{i,h(i)}$$</span> where the first summation is over <i>all</i> permutations <span class="math-container">$h:[n]\to[n]$</span>, and the second is only over all <i>cyclic</i> permutations <span class="math-container">$h:[n]\to[n]$</span>. <blockquote> <b>Question:</b> Why HAM is <b>not</b> a monotone projection PER? Or it still is? </blockquote> I am not asking for <i>proofs</i>, just for intuitive reasons. <p> Motivation: the largest known monotone circuit lower bound for PER (proved by Razborov) remains "only" <span class="math-container">$n^{\Omega(\log n)}$</span>. On the other hand, results of [Valiant](https://web.vu.lt/mif/s.jukna/boolean/valiant-completeness.pdf) imply that <span class="math-container">$$\mbox{CLIQUE_n is a monotone projection of HAM_{m}}$$</span> where <span class="math-container">$$\mbox{CLIQUE}_n(x)=\sum_{S}\prod_{i &lt; j\in S}x_{i,j}$$</span> with the summation is over all subsets <span class="math-container">$S\subseteq [n]$</span> of size <span class="math-container">$|S|=\sqrt{n}$</span>. I myself couldn't get a "simple, direct" reduction form these general results, but [Alon and Boppana](https://web.vu.lt/mif/s.jukna/boolean/Alon-Boppana.pdf) claim (in Sect. 5) that already <span class="math-container">$m=25n^2$</span> is sufficient for this reduction. <p> But wait: it is well known that CLIQUE requires monotone circuits of size <span class="math-container">$2^{n^{\Omega(1)}}$</span> (first proved by Alon and Boppana using Razborov's method). <p> So, were HAM a monotone projection of PER, we would have <span class="math-container">$2^{n^{\Omega(1)}}$</span> lower bound also for PER. <p> Actually, <i>why</i> HAM is not even a <b>non-monotone</b> projection of PER? Over the boolean semiring, the former is <b>NP</b>-complete, while the latter is in <b>P</b>. But why? Where is a place where being <b>cyclic</b> for a permutation makes it so special? <p> <b>P.S.</b> One obvious difference could be: HAM covers [n] by just one (long) cycle, whereas PER can use may disjoint cycles for this. Thus, to project PER to HAM the hard direction seems to be: ensure that the <i>absence</i> of a Hamiltonian cycle implies the absence of any covering with disjoint cycles in the new graph. Is this the reason for HAM not being a projection of PER? <p> <b>P.P.S.</b> Actually, Valiant proved a more impressing result: every polynomial <span class="math-container">$f(x)=\sum_{u\subseteq [n]}c_u\prod_{i\in u}x_i$</span> with <span class="math-container">$c_u\in\{0,1\}$</span>, whose coefficients <span class="math-container">$c_u$</span> are p-time computable, is a projection (not necessarily monotone if the algo is non-monotone) of HAM<span class="math-container">$_m$</span> for <span class="math-container">$m$</span> = poly<span class="math-container">$(n)$</span>. PER also has this property, but only over fields of characteristic <span class="math-container">$\neq 2$</span>. So, in this sense, HAM and PER <i>are</i> indeed "similar", unless we are not in GF(2) where, as Bruno remembered, PER turns to DETERMINANT, and is easy. https://cstheory.stackexchange.com/q/8918 23 Monotone arithmetic circuits Kaveh https://cstheory.stackexchange.com/users/186 2011-11-10T22:32:39Z 2021-12-16T10:32:52Z <p>The state of our knowledge about <a href="http://en.wikipedia.org/wiki/Arithmetic_circuit_complexity#Lower_bounds" rel="nofollow noreferrer">general arithmetic circuits</a> 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 exponential size lower-bounds for <a href="http://en.wikipedia.org/wiki/Monotone_circuit#History" rel="nofollow noreferrer">monotone Boolean circuits</a>. </p> <blockquote> <p>What do we know about <em>monotone</em> arithmetic circuits? Do we have similar good lower-bounds for them? If not, what is the essential difference that doesn't allow us to get similar lower-bounds for monotone arithmetic circuits?</p> </blockquote> <p>The question is inspired by comments on <a href="https://cstheory.stackexchange.com/q/8853/186">this question</a>.</p> https://cstheory.stackexchange.com/q/16471 22 Lower bound for determinant and permanent Nikhil https://cstheory.stackexchange.com/users/256 2013-02-14T19:36:38Z 2013-02-18T16:19:52Z <p>In light of the recent <a href="http://eccc.hpi-web.de/report/2013/026/">chasm at depth-3</a> result (which among other things yields a $2^{\sqrt{n}\log{n}}$ depth-3 arithmetic circuit for the $n \times n$ determinant over $\mathbb{C}$), I have the following questions : Grigoriev and Karpinski <a href="http://www.google.co.in/url?sa=t&amp;rct=j&amp;q=grigoriev%20karpinski%20%20an%20exponential%20lower%20bound%20for%20depth%203&amp;source=web&amp;cd=1&amp;cad=rja&amp;ved=0CC4QFjAA&amp;url=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.2768&amp;ei=szodUY_yF8L-rAfD_YDYCg&amp;usg=AFQjCNFgR3k4wXZyeUQVgqXgh81Rf38QBw&amp;bvm=bv.42452523,d.bmk">proved</a> an $2^{\Omega{(n)}}$ lower bound for any depth-3 arithmetic circuit computing the Determinant of $n \times n$ matrices over finite fields (which I guess, also holds for the Permanent). <a href="http://en.wikipedia.org/wiki/Computing_the_permanent#Ryser_formula">Ryser's formula</a> for computing the Permanent gives a depth-3 arithmetic circuit of size $O(n^2 2^n) = 2^{O(n)}$. This shows that the result is essentially tight for depth-3 circuits for the Permanent over finite fields. I have two questions:</p> <p>1) Is there a depth-3 formula for the determinant analogous to Ryser's formula for the Permanent?</p> <p>2) Does a lower bound on the size of arithmetic circuits computing the Determinant polynomial \textit{always} yield a lower bound for the Permanent polynomial?(Over $\mathbb{F}_2$ they are the same polynomials).</p> <p>Though my question currenly is regarding these polynomials over finite fields, I would also like to know the status of these questions over arbitrary fields.</p> https://cstheory.stackexchange.com/q/27306 21 Arithmetic circuits with just one threshold gate Stasys https://cstheory.stackexchange.com/users/5788 2014-11-02T16:58:15Z 2014-11-14T13:21:28Z <p>When restricted to $0$-$1$ inputs, every $\{+,\times\}$-circuit $F(x_1,\ldots,x_n)$ computes some function $F:\{0,1\}^n\to \mathbb{N}$. To obtain a <i>boolean</i> function, we can just add one fanin-1 threshold gate as the output gate. On input $a\in\{0,1\}^n$, the resulting <i>threshold</i> $\{+,\times\}$-<i>circuit</i> then outputs $1$ if $F(a)\geq t$, and outputs $0$ if $F(a)\leq t-1$; the threshold $t=t_n$ can be any positive integer, which may dependent on $n$ but not on input values. The resulting circuit computes some (monotone) <i>boolean</i> function $F':\{0,1\}^n\to \{0,1\}$.</p> <blockquote> <b>Question:</b> Can threshold $\{+,\times\}$-circuits be efficiently simulated by $\{\lor,\land\}$-circuits? </blockquote> <p>Under "efficiently" I mean "with at most a polynomial increase of size." The answer is clear "yes" for threshold $t=1$: just replace $+$ by $\lor$, $\times$ by $\land$, and remove the last threshold gate. That is, $\{\lor,\land\}$-circuits are in fact threshold-$1$ $\{+,\times\}$-circuits. But what about larger thresholds, say, $t=2$? <p></p> <p>One can define arithmetic analogues $\#C$ of most boolean circuit classes $C$ by just using $+$ instead of OR, $\times$ instead of AND, and $1-x_i$ instead of $\bar{x}_i$. For example, $\#AC^0$ circuits are $\{+,\times\}$-circuits of constant depth with unbounded fanin $+$ and $\times$ gates, and inputs $x_i$ and $1-x_i$. <a href="http://www.sciencedirect.com/science/article/pii/S0022000099916756" rel="nofollow">Agrawal, Allender and Datta have shown</a> that threshold $\#AC^0$ = $TC^0$. (Recall that $AC^0$ itself is a <i>proper</i> subset of $TC^0$; take, say, the Majority function.) In other words, constant-depth threshold circuits can be efficiently simulated by constant-depth $\{+,-,\times\}$-circuits, with just a single threshold gate! Note, however, that my question is about <b>monotone</b> circuits (no Minus "$-$" as gates, and even no $1-x_i$ as inputs). Can one (last) threshold gate be so powerful also then? I don't know this stuff, so any related pointers are welcome. <p> <b>N.B.</b> There is yet another interesting related <a href="http://www.sciencedirect.com/science/article/pii/S0020019097000070" rel="nofollow">result</a> due to Arnold Rosenbloom: $\{+,\times\}$-circuits with just one <i>monotone</i> function $g:\mathbb{N}^2\to\{0,1\}$ as output gate can compute every slice function with $O(n)$ gates. A slice function is a monotone boolean function which, for some fixed $k$, outputs $0$ (resp. $1$) on all inputs with less (resp., more) than $k$ ones. On the other hand, easy counting shows that most slice functions require general $\{\lor,\land,\neg\}$-circuits of exponential size. Thus, one "innocent" additional output gate <i>can</i> make monotone circuits omnipotent! My question asks whether this can also happen when $g:\mathbb{N}\to\{0,1\}$ is a fanin-$1$ threshold gate. <hr> <b>ACTUALIZATION</b> (added 03.11.2014): Emil Je&#345;&#225;bek has shown (via an amazingly simple construction, see his answer below) that the answer is "yes" as long as $t\leq n^c$ for a constant $c$. So, the question remains open only for <b>super-polynomial</b> (in $n$) thresholds. <p> Usually, in applications, only large thresholds do work: we usually need thresholds of the form $2^{n^{\epsilon}}$ for $\epsilon &gt; 0$. Say, if $F:\{0,1\}^n\to \mathbb{N}$ <i>counts</i> the number of $s$-$t$ paths in graph specified by the $0$-$1$ input, then for $t=m^{m^2}$ with $m\approx n^{1/3}$, the threshold-$t$ version of $F$ <i>solves</i> the existence of a Hamiltonian $s$-$t$ path problem on $m$-vertex graphs (see, e.g. <a href="http://www.cs.cmu.edu/~flac/pdf/NumberP.pdf" rel="nofollow">here</a>). <p> (Added 14.11.2014): Since Emil answered a big portion of my question, and since the case of exponential thresholds is not in sight, I now accept this Emil's (very nice) answer.</p> <hr> https://cstheory.stackexchange.com/q/25624 16 What are bounded-treewidth circuits good for? a3nm https://cstheory.stackexchange.com/users/4795 2014-08-28T12:52:09Z 2018-10-29T16:40:04Z <p>One can talk of the <a href="https://en.wikipedia.org/wiki/Treewidth" rel="noreferrer">treewidth</a> of a Boolean circuit, defining it as the treewidth of the "moralized" graph on wires (vertices) obtained as follows: connect wires <span class="math-container">$a$</span> and <span class="math-container">$b$</span> whenever <span class="math-container">$b$</span> is the output of a gate having <span class="math-container">$a$</span> as input (or vice-versa); connect wires <span class="math-container">$a$</span> and <span class="math-container">$b$</span> whenever they are used as inputs to the same gate. <strong>Edit:</strong> one can equivalently define the treewidth of the circuit as that of the graph representing it; if we use associativity to rewite all AND and OR gates to have fan-in at most two, the treewidth according to either definition is the same up to a factor <span class="math-container">$3$</span>.</p> <p>There is at least one problem that is known to be untractable in general but tractable on Boolean circuits of bounded treewidth: given a probability for each of the input wires to be set to 0 or 1 (independently from the others), compute the probability that a certain output gate is 0 or 1. This is generally #P-hard by a reduction from e.g. #2SAT, but it can be solved in PTIME on circuits whose treewidth is assumed to be less than a constant, using the <a href="https://en.wikipedia.org/wiki/Junction_tree_algorithm" rel="noreferrer">junction tree algorithm</a>.</p> <p>My question is to know whether there are <em>other</em> problems, beyond probabilistic computation, that are known to be intractable in general but tractable for bounded-treewidth circuts, or whose complexity can be described as a function of the circuit size and also of its treewidth. My question is not specific to the Boolean case; I am also interested in <a href="https://en.wikipedia.org/wiki/Arithmetic_circuit" rel="noreferrer">arithmetic circuits</a> over other semirings. Do you see any such problems?</p> https://cstheory.stackexchange.com/q/27190 15 Any polynomial which is hard to count but easy to decide? Stasys https://cstheory.stackexchange.com/users/5788 2014-10-24T16:17:51Z 2014-10-28T10:33:58Z <p>Every monotone <a href="http://en.wikipedia.org/wiki/Arithmetic_circuit_complexity" rel="nofollow">arithmetic circuit</a>, i.e. a $\{+,\times\}$-circuit, computes some multivariate polynomial $F(x_1,\ldots,x_n)$ with nonnegative integer coefficients. Given a polynomial $f(x_1,\ldots,x_n)$, the circuit</p> <ul> <li> <b>computes</b> $f$ if $F(a)=f(a)$ holds for all $a\in \mathbb{N}^n$; <li> <b>counts</b> $f$ if $F(a)=f(a)$ holds for all $a\in\{0,1\}^n$; <li> <b>decides</b> $f$ if $F(a)&gt;0$ exactly when $f(a)&gt;0$ holds for all $a\in\{0,1\}^n$. </ul> <p>I know explicit polynomials $f$ (even multilinear) showing that the circuit-size gap "computes/counts" can be exponential. My question concerns the gap "counts/decides".</p> <blockquote> <b>Question 1:</b> Does anybody know of any polynomial $f$ which is exponentially harder to count than to decide by $\{+,\times\}$-circuits? </blockquote> <p>As a possible candidate, one could take the PATH polynomial whose variables correspond to edges of the complete graph $K_n$ on $\{1,\ldots,n\}$, and each monomial corresponds to a simple path from node $1$ to node $n$ in $K_n$. This polynomial can be <i>decided</i> by a circuit of size $O(n^3)$ implementing, say, the Bellman-Ford dynamic programming algorithm, and it is relatively easy to show that every $\{+,\times\}$-circuit <i>computing</i> PATH must have size $2^{\Omega(n)}$. <p> On the other hand, every circuit <i>counting</i> PATH solves the $\#$PATH problem, i.e. counts the number of $1$-to-$n$ paths in the specified by the corresponding $0$-$1$ input subgraph of $K_n$. This is a so-called <a href="http://de.wikipedia.org/wiki/Sharp-P" rel="nofollow">$\#$<b>P</b>-complete problem</a>. So, we all "believe" that PATH cannot have any counting $\{+,\times\}$-circuits of polynomial size. The "only" problem is to <i>prove</i> this ... <p> I can show that every $\{+,\times\}$-circuit counting a related <i> Hamiltonian path</i> polynomial HP requires exponential size. Monomials of this polynomial correspond to $1$-to-$n$ paths in $K_n$ containing all nodes. Unfortunately, the <a href="http://epubs.siam.org/doi/abs/10.1137/0208032" rel="nofollow">reduction</a> of $\#$HP to $\#$PATH by Valiant requires to compute the inverse of the Vandermonde matrix, and hence cannot be implemented by a $\{+,\times\}$-circuit.</p> <blockquote> <b>Question 2:</b> Has anybody seen a <b>monotone</b> reduction of $\#$HP to $\#$PATH? </blockquote> <p>And finally: </p> <blockquote> <b>Question 3:</b> Was a "monotone version" of the class $\#$<b>P</b> considered at all? </blockquote> <p><b>N.B.</b> Note that I am talking about a very restricted class of circuits: <i>monotone</i> arithmetic circuits! In the class of $\{+,-,\times\}$-circuits, Question 1 would be just unfair to ask at all: no lower bounds larger than $\Omega(n\log n)$ for such circuits, even when required to compute a given polynomial on all inputs in $\mathbb{R}^n$, are known. Also, in the class of such circuits, a "structural analogue" of Question 1 -- are there $\#$<b>P</b>-complete polynomials which can be decided by poly-size $\{+,-,\times\}$-circuits? -- has an affirmative answer. Such is, for example, the permanent polynomial PER$=\sum_{h\in S_n}\prod_{i=1}^n x_{i,h(i)}$. <p> <b>ADDED:</b> Tsuyoshi Ito answered Question 1 with a very simple trick. Still, Questions 2 and 3 remain open. The counting status of PATH is interesting in its own both because it is a standard DP problem and because it is #P-complete. </p> https://cstheory.stackexchange.com/q/1590 14 Machine characterization of $SAC^i$ Shiva Kintali https://cstheory.stackexchange.com/users/344 2010-09-22T19:57:56Z 2015-10-22T03:24:30Z <p>$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 is known that $SAC^i$ for $i \geq 1$ is closed under complement and $SAC^0$ is not. Also, $SAC^1 = LogCFL$ and hence has a machine characterization, since <a href="http://en.wikipedia.org/wiki/LOGCFL">LogCFL</a> is the set of languages accepted by an $O({\log}n)$ space bounded and polynomial time bounded auxiliary PDA. Are there similar machine characterizations of $SAC^i$ for $i \geq 2$ ?</p> https://cstheory.stackexchange.com/q/37772 14 VC dimension of polynomials over tropical semirings? Stasys https://cstheory.stackexchange.com/users/5788 2017-03-15T17:40:48Z 2022-01-02T13:41:18Z <p>As in <a href="https://cstheory.stackexchange.com/questions/37632/adlemans-theorem-over-infinite-semirings">this</a> question, I am interested the $\mathbf{BPP}$ vs. $\mathbf{P}$/$\mathrm{poly}$ <a href="https://en.wikipedia.org/wiki/P/poly" rel="nofollow noreferrer">problem</a> for <i>tropical</i> $(\max,+)$ and $(\min,+)$ circuits. This question reduces to showing upper bounds for the VC dimension of polynomials over the tropical semirings (see Theorem 2 below). <p> Let $R$ be a semiring. A <i>zero-pattern</i> of a sequence $(f_1,\ldots,f_m)$ of $m$ polynomials in $R[x_1,\ldots,x_n]$ is a subset $S\subseteq \{1,\ldots,m\}$ for which there exist $x\in R^n$ and $y\in R$ such that for all $i=1,\ldots,m$, $f_i(x)= y$ iff $i\in S$. That is, the graphs of exactly those polynomials $f_i$ with $i\in S$ must hit the point $(x,y)\in R^{n+1}$. ("Zero-pattern" because the condition $f_i(x)=y$ can be replaced by $f_i(x)-y=0$.) Let $Z(m)$ = the maximum possible number of zero-patterns of a sequence of $m$ polynomials of degree at most $d$. Hence, $0\leq Z(m)\leq 2^m$. The <i>Vapnik-Chervonenkis dimension</i> of degree $d$ polynomials is $VC(n,d) := \max\{m\colon Z(m)=2^m\}$. <p> <b>Remark:</b> Usually, the VC dimension is defined for a family ${\cal F}$ of sets as the largest cardinality $|S|$ of a set $S$ such that $\{F\cap S\colon F\in{\cal F}\}=2^S$. To fit into this frame, we can associate with every pair $(x,y)\in R^{n+1}$ the set $F_{x,y}$ of all polynomials of $f$ degree $\leq d$ for which $f(x)=y$ holds. Then the VC dimension of the family ${\cal F}$ of all such sets $F_{x,y}$ is exactly $VC(n,d)$. <p> A trivial upper bound on $m=VC(n,d)$ is $m\leq n\log |R|$ (we need at least $2^m$ distinct vectors $x\in R^n$ to have all $2^m$ possible patterns), but it is useless in infinite semirings. To have good upper bounds on the VC dimension, we need good upper bounds on $Z(m)$. Over <i>fields</i>, such bounds are known.</p> <p><blockquote> <b>Theorem 1:</b> Over any <i>field</i> $R$, we have $Z(m)\leq \binom{md+n}{n}$. </blockquote> Similar upper bounds were earlier proved by <a href="http://www.ams.org/journals/proc/1964-015-02/S0002-9939-1964-0161339-9/" rel="nofollow noreferrer">Milnor</a>, <a href="http://www.sciencedirect.com/science/article/pii/0304397583900026" rel="nofollow noreferrer">Heintz</a> and <a href="http://www.ams.org/journals/tran/1968-133-01/S0002-9947-1968-0226281-1/" rel="nofollow noreferrer">Warren</a>; their proofs use heavy techniques from real algebraic geometry. In contrast, a half-page proof of Theorem 1 by <a href="http://www.ams.org/journals/jams/2001-14-03/S0894-0347-01-00367-8/" rel="nofollow noreferrer">Ronyai, Babai and Ganapathy</a> (which we give below) is a simple application of linear algebra. <p></p> <p>By looking for small $m$'s satisfying $\binom{md+n}{n} &lt; 2^m$, we obtain that $VC(n,d)=O(n\log d)$ holds over any <i>field</i>. In view of the $\mathbf{BPP}$ vs. $\mathbf{P}$/$\mathrm{poly}$, important here is that the dimension is only <i>logarithmic</i> in the degree $d$. This is important because circuits of polynomial size can compute polynomials of exponential degree, and because a result of Haussler in PAC learning (Corollary 2 on page 114 of <a href="http://www.sciencedirect.com/science/article/pii/089054019290010D" rel="nofollow noreferrer">this paper</a>) yields the following (where we assume that deterministic circuits are allowed to use majority vote to output their values). <blockquote> <b>Theorem 2:</b> $\mathbf{BPP}\subseteq \mathbf{P}/\mathrm{poly}$ holds for circuits over any semiring $R$, where $VC(n,d)$ is only polynomial in $n$ and $\log d$. </blockquote> See <a href="http://www.thi.informatik.uni-frankfurt.de/~jukna/ftp/haussler.html" rel="nofollow noreferrer"><b>here</b></a> on how Haussler's result implies Theorem 2. <p> In particular, by Theorem 1, $\mathbf{BPP}\subseteq \mathbf{P}/\mathrm{poly}$ holds over any field. (Interesting is here only the case of <i>infinite</i> fields: for finite ones, much simpler arguments work: Chernoff bound then does the work.) But what about (infinite) semirings that are <i>not</i> fields, or even not rings? Motivated by dynamic programming, I am mainly interested in tropical $(\max,+)$ and $(\min,+)$ semirings, but other "non-field" (infinite) semirings are interesting as well. Note that, over the $(\max,+)$ semiring, a polynomial $f(x)=\sum_{a\in A} c_a\prod_{i=1}^n x_i^{a_i}$ with $A\subseteq\mathbb{N}$ and $c_a\in \mathbb{R}$, turns into the maximization problem $f(x)=\max_{a\in A}\ \{c_a+a_1x_1+a_2x_2+\cdots+a_nx_n\}$; the degree of $f$ is (as customary) the maximum of $a_1+\cdots+a_n$ over all $a\in A$.</p> <blockquote> <b>Question :</b> Is the VC dimension of degree $\leq d$ polynomials over tropical semirings polynomial in $n\log d$? </blockquote> <p>I admit, this can be a rather hard question to expect a quick answer: tropical algebra is rather "crazy". But perhaps somebody has some ideas on why (if any) tropical polynomials could produce more zero-patterns than real polynomials? Or why they "shouldn't"? Or some related references. <p> Or, perhaps, the proof of Babai, Ronyai, and Ganapathy (below) can be somehow "twisted" to work over tropical semirings? Or over any other infinite semirings (which are not fields)? <p> <b>Proof of Theorem 1:</b> Assume that a sequence $(f_1,\ldots,f_m)$ has $p$ different zero-patterns, and let $v_1,\ldots,v_p\in R^n$ be witnesses to these zero-patterns. Let $S_i=\{k\colon f_k(v_i)\neq 0\}$ be a zero-pattern witnessed by the $i$-th vector $v_i$, and consider the polynomials $g_i:=\prod_{k\in S_i}f_k$. We claim that these polynomials are linearly independent over our field. This claim completes the proof of the theorem since each $g_i$ has degree at most $D:=md$, and the dimension of the space of polynomials of degree at most $D$ is $\binom{n+D}{D}$. To prove the claim, it is enough to note that $g_i(v_j)\neq 0$ if and only if $S_i\subseteq S_j$. Suppose contrariwise that a nontrivial linear relation $\lambda_1 g_i(x)+\cdots+\lambda_p g_p(x)=0$ exists. Let $j$ be a subscript such that $|S_j|$ is minimal among the $S_i$ with $\lambda_i\neq 0$. Substitute $v_j$ in the relation. While $\lambda_jg_j(v_j)\neq 0$, we have $\lambda_ig_i(v_j)=0$ for all $i\neq j$, a contradiction. $\Box$</p> https://cstheory.stackexchange.com/q/25198 14 A course for learning algebraic complexity shen https://cstheory.stackexchange.com/users/26584 2014-07-10T13:54:28Z 2014-07-10T16:22:34Z <p>I want to learn about algebraic algorithms and complexity thoery. In particular, I am interested in PIT.</p> <p>Is there a set of lecture notes, books, papers and surveys for students who have read standard textbook about theory like Sipser's book or the Arora-Barak's complexity textbook. </p> <p>The set of references will includes recent advanced results. </p> https://cstheory.stackexchange.com/q/33503 14 Monotone arithmetic circuit complexity of elementary symmetric polynomials? Stasys https://cstheory.stackexchange.com/users/5788 2016-01-04T18:59:21Z 2016-01-06T16:27:07Z <p>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 complexity of this polynomial. A simple dynamic programming algorithm (as well as Fig. 1 below) gives a $(+,\times)$ circuit with $O(kn)$ gates.</p> <blockquote> <b> Question:</b> Is a lower bound of $\Omega(kn)$ known? </blockquote> <p>A $(+,\times)$ circuit is <i>skew</i> if at least one of the two inputs of each product gate is a variable. Such a circuit is actually the same as switching-and-rectifying network (a directed acyclic graph with some edges labeled by variables; each s-t path gives the product of its labels, and the output is the sum of over all s-t paths). Already 40 years ago, Markov proved a surprisingly tight result: a minimal monotone arithmetic skew circuit for $S_k^n$ has <b>exactly</b> $k(n-k+1)$ product gates. The <i>upper</i> bound follows from Fig. 1: <a href="https://i.stack.imgur.com/SNBOw.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/SNBOw.png" alt="enter image description here"></a> <p> But I haven't seen any attempt to prove such a lower bound for non-skew circuits. Is this just our "arrogance", or are there some inherent difficulties observed along the way? <p> P.S. I know that $\Omega(n\log n)$ gates are necessary to simultaneously compute all $S_1^n,\ldots,S_n^n$. This follows from the lower bound on the size of monotone boolean circuits sorting the 0-1 input; see page 158 of <a href="http://eccc.hpi-web.de/static/books/The_Complexity_of_Boolean_Functions/" rel="nofollow noreferrer">Ingo Wegener's book</a>. The <a href="https://en.wikipedia.org/wiki/Sorting_network" rel="nofollow noreferrer">AKS sorting network</a> also implies that $O(n\log n)$ gates are sufficient in this (boolean) case. Actually, <a href="http://www.sciencedirect.com/science/article/pii/030439758390110X" rel="nofollow noreferrer">Baur and Strassen</a> have proved a tight bound $\Theta(n\log n)$ on the size of <i>non-monotone</i> arithmetic circuit for $S_{n/2}^n$. But what about <i>monotone</i> arithmetic circuits?</p> https://cstheory.stackexchange.com/q/37632 13 Adleman's theorem over infinite semirings? Stasys https://cstheory.stackexchange.com/users/5788 2017-02-25T17:23:03Z 2017-03-06T11:52:35Z <p>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 computed by a deterministic boolean circuit of size polynomial in $M$ and $n$; actually, of size $O(nM)$. <blockquote> <b>General Question :</b> Over what other (than boolean) semirings does $\mathrm{BPP}\subseteq \mathrm{P/poly}$ hold? </blockquote></p> <p>To be a bit more specific, a <i>probabilistic</i> circuit $\mathsf{C}$ over a semiring $(S,+,\cdot,0,1)$ uses its "addition" $(+)$ and "multiplication'' $(\cdot)$ operations as gates. Inputs are input variables $x_1,\ldots,x_n$ and possibly some number of additional random variables, which take the values $0$ and $1$ independently with probability $1/2$; here $0$ and $1$ are, respectively, the additive and multiplicative identities of the semiring. Such a circuit $\mathsf{C}$ <i>computes</i> a given function $f:S^n\to S$ if for every $x\in S^n$, $\mathrm{Pr}[\mathsf{C}(x)=f(x)]\geq 2/3$. <p> The <i>voting function</i> $\mathrm{Maj}(y_1,\ldots,y_m)$ of $m$ variables is a partial function whose value is $y$ if the element $y$ appears more than $m/2$ times among the $y_1,\ldots,y_m$, and is undefined, if no such element $y$ exists. A simple application of Chernoff's and union bounds yields the following.</p> <blockquote> <b>Majority Trick:</b> If a probabilistic circuit $\mathsf{C}$ computes a function $f:S^n\to S$ on a finite set $X\subseteq S^n$, then there are $m=O(\log|X|)$ realizations $C_1,\ldots,C_m$ of $\mathsf{C}$ such that $f(x)=\mathrm{Maj}(C_1(x),\ldots,C_m(x))$ holds for all $x\in X$. </blockquote> <p>Over the boolean semiring, the voting function $\mathrm{Maj}$ is the majority function, and has small (even monotone) circuits. So, Adleman's theorem follows by taking $X=\{0,1\}^n$. <p> But what about other (especially, infinite) semirings? What about the <i>arithmetic</i> semiring $(\mathbb{N},+,\cdot,0,1)$ (with usual addition and multiplication)?</p> <blockquote> <b>Question 1:</b> Does $\mathrm{BPP}\subseteq \mathrm{P/poly}$ hold over the arithmetic semiring? </blockquote> <p>Although I bet for "yes", I cannot show this. <p> <b>Remark:</b> I am aware of this <a href="http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/random-circuits.pdf" rel="nofollow noreferrer">paper</a> where the authors claim $\mathrm{BPP}\subseteq \mathrm{P/poly}$ over the real field $(\mathbb{R},+,\cdot,0,1)$. They deal with <i>non-monotone</i> arithmetic circuits, and also arrive (in Theorem 4) to circuits with the voting function $\mathrm{Maj}$ as an output gate. But how to simulate this $\mathrm{Maj}$-gate by an arithmetic circuit (be it monotone or not)? I.e. how to get their Corollary 3? </p> <p>Actually, the following simple argument told to me by Sergey Gashkov (from Moscow University) seems to show that this is <i>impossible</i> (at least for circuits able to compute only <i>polynomials</i>). Suppose we can express $\mathrm{Maj}(x,y,z)$ as a polynomial $f(x,y,z)=ax+by+cz+ h(x,y,z)$. Then $f(x,x,z)=x$ implies $c=0$, $f(x,y,x)=x$ implies $b=0$, and $f(x,y,y)=y$ implies $a=0$. This holds because, over fields of zero characteristic, equality of polynomial-functions means equality of coefficients. Note that in Question 1, the range of probabilistic circuits, and hence, the domain of the $\mathrm{Maj}$-gate is <i>infinite</i>. I therefore have an impression that the linked paper deals only with arithmetic circuits computing functions $f:\mathbb{R}^n\to Y$ with small finite ranges $Y$, like $Y=\{0,1\}$. Then $\mathrm{Maj}:Y^m\to Y$ is indeed easy to compute by an arithmetic circuit. But what if $Y=\mathbb{R}$? <hr> <b>Correction</b> [6.03.2017]: Pascal Koiran (one of the authors of this paper) pointed to me that their model is more powerful than just arithmetic circuits: they allow Sign-gates (outputing $0$ or $1$ depending on whether the input is negative of not). So, the voting function Maj <i>can</i> be simulated in this model, and I take back my "confusion". </p> <hr> <p><p> In the context of dynamic programming, especially interesting is the same question for <i>tropical</i> min-plus and max-plus semirings $(\mathbb{N}\cup\{+\infty\}, \min, +, +\infty,0)$ and $(\mathbb{N}\cup\{-\infty\}, \max, +, -\infty,0)$.</p> <blockquote> <b>Question 2:</b> Does $\mathrm{BPP}\subseteq \mathrm{P/poly}$ hold over tropical semirings? </blockquote> <p>Held $\mathrm{BPP}\subseteq \mathrm{P/poly}$ in these two semirings, this would mean that randomness cannot speed-up so-called "pure" dynamic programming algorithms! These algorithms only use Min/Max and Sum operations in their recursions; Bellman-Ford, Floyd-Warshall, Held-Karp, and many other prominent DP algorithms <i>are</i> pure. <p> So far, I can only answer Question 2 (affirmatively) under the <i>one-sided</i> error scenario, when we additionally require $\mathrm{Pr}[\mathsf{C}(x) &lt; f(x)]=0$ over the min-plus semiring (minimization), or $\mathrm{Pr}[\mathsf{C}(x) &gt; f(x)]=0$ over the max-plus semiring (maximization). That is, we now require that the the randomized tropical circuit can never produce any better than optimum value; it can, however, err by giving some worse-than-optimal values. My questions are, however, under the <i>two-sided error</i> scenario. </p> <p><hr> <b>P.S.</b> [added 27.02.2017]: <a href="http://www.thi.informatik.uni-frankfurt.de/~jukna/ftp/adleman2.html" rel="nofollow noreferrer"><b>Here</b></a> is my attempt to answer Question 1 (affirmatively). The idea is to combine a simplest version of the "combinatorial Nullstellensatz" with an estimate for the Zarankiewicz problem for n-partite hypergraps, due to Erdos and Spencer. Modulo this latter result, the entire argument is elementary. <p> Note that Question 2 still remains open: the "naive Nullstellensatz" (at least in the form I used) does not hold in tropical semirings. </p> https://cstheory.stackexchange.com/q/16443 12 Arithmetic circuits with $\min$, $\max$, and average over $[0,1]$ Shaull https://cstheory.stackexchange.com/users/7531 2013-02-11T15:56:45Z 2013-02-13T21:20:21Z <p>Consider a circuit that takes as inputs numbers in $[0,1]$, and has gates that consist of the functions $\max(x, y)$, $\min(x, y)$, $1 - x$, and $\frac{x+y}{2}$. The output of the circuit is then also a number in $[0,1]$.</p> <p>Does anyone know if this model, or a closely related model, has been studied? </p> <p>Specifically, I'm trying to solve the satisfiability problem for this circuit, namely computing the maximum value that can be attained by this circuit (it indeed attains a maximum, as it represents a continuous function in a compact domain).</p> <p>Remark: my study of this model is via weighted temporal logics, so any models that relate to the latter might also come in handy.</p> https://cstheory.stackexchange.com/q/34052 12 Are arithmetic circuits weaker than boolean? Stasys https://cstheory.stackexchange.com/users/5788 2016-03-13T21:09:23Z 2016-03-16T10:17:09Z <p>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}\,,$$ and $B(f)$ denote the minimum size of a (non-monotone) boolean $(\lor,\land,\neg)$ circuit computing the<b> boolean version</b> $f_b$ of $f$ defined by: $$f_b(x_1,\ldots,x_n)=\bigvee_{e\in E}\ \bigwedge_{i\colon e_i\neq 0} x_i\,.$$</p> <blockquote> Are polynomials $f$ known for which $B(f)$ is smaller than $A(f)$? </blockquote> <p>If we consider <i>monotone</i> versions of circuits -- no Minus $(-)$ and no Not $(\neg)$ gates -- then $B(f)$ can be even <b>exponentially</b> smaller than $A(f)$: take, for example, the shortest s-t path polynomial $f$ on $K_n$; then $B(f)=O(n^3)$ and $A(f)=2^{\Omega(n)}$. But what happens in the "non-monotone world"? Of course, <b>big</b> gaps cannot be known just because we do not have large lower bounds on $A(f)$. But perhaps there are at least some small gaps known? <hr> NOTE (15.03.2016) In my question, I do not specified how large coefficients $c_e$ are allowed. Igor Sergeev remembered me that, for example, the following (univariate) polynomial $f(z)=\sum_{j=1}^m 2^{2^{jm}} z^j$ has $A(f)=\Omega(m^{1/2})$ (Strassen and people of his group). But $B(f)=0$ for this polynomial, since $f_b(z)=z$. We can obtain fron $f$ a <i>multivariate</i> polynomial $f'(x_1,\ldots,x_n)$ of $n=\log m$ variables using using Kronecker substitution. Associate with every exponent $j$ a monomial $X_j=\prod_{i:a_i=1}x_i$, where $(a_1,\ldots,a_n)$ are the 0-1 coefficients of the binary representation of $j$. Then the desired polynomial is $f'=\sum_{j=1}^m c_j X_j$, and we have that $$A(f')+n\geq A(f)=\Omega(m^{1/2})=2^{\Omega(n)}.$$ But the boolean version of $f'$ is just an OR of variables, so $B(f')\leq n-1$, and we have an even exponential gap. Thus, if magnitude of coefficients can be triple-exponential in the number $n$ of variables then the gap $A(f)/B(f)$ <b>can</b> be shown to be even exponential. (Actually, not the magnitude itself -- more the algebraic dependence of the coefficients.) This is why the real problem with $A(f)$ is the case of <i>small</i> coefficients (ideally, only 0-1). But in this case, as Joshua recalled, the lower bound $A(f)=\Omega(n\log n)$ of Strassen and Baur (with 0-1 coefficients) remains the best what we have today. </p> https://cstheory.stackexchange.com/q/27510 11 Straight line complexity of monomials Gorav Jindal https://cstheory.stackexchange.com/users/16008 2014-11-19T11:16:38Z 2014-11-21T10:08:50Z <p>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 monomials which appear in $f$ with non-zero coefficient. </p> <blockquote> <p>Is it true that $\forall m\in F:L(m)\le L(f)$?</p> </blockquote> <p>Even some weaker upper bound for $L(m)$ is known?</p> https://cstheory.stackexchange.com/q/17637 11 Determinants and Matrix Multiplication - Similarity and differences in algorithmic complexity and arithmetic circuit size Turbo https://cstheory.stackexchange.com/users/1812 2013-05-15T17:25:01Z 2013-05-23T07:11:19Z <p>I am trying to understand the relation between algorithmic complexity and circuit complexity of Determinants and Matrix Multiplication.</p> <p>It is known that the determinant of an $n\times n$ matrix can be <a href="http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Matrix_algebra" rel="nofollow noreferrer">computed</a> in $\tilde{O}(M(n))$ time, where $M(n)$ is the minimum time required to multiply any two $n\times n$ matrices. It is also known that the best circuit complexity of determinants is <a href="http://en.wikipedia.org/wiki/Arithmetic_circuit_complexity#Upper_bounds" rel="nofollow noreferrer">polynomial</a> at depth $O(\log^{2}(n))$ and <a href="http://people.cs.uchicago.edu/~razborov/files/depth3.ps" rel="nofollow noreferrer">exponential</a> at depth 3. But the circuit complexity of matrix multiplication, for any constant depth, is only polynomial.</p> <p>Why is there a difference in circuit complexity for determinants and matrix multiplication while it is known that from an algorithm perspective determinant calculation is <a href="http://www4.ncsu.edu/~kaltofen/bibliography/04/KaVi04_2697263.pdf" rel="nofollow noreferrer">similar</a> to matrix multiplication? Specifically, why do the circuit complexities have an exponential gap at depth-$3$? </p> <p>Probably, the explanation is simple but I do not see it. Is there an explanation with 'rigor'?</p> <p>Also look in: <a href="https://cstheory.stackexchange.com/questions/12448/smallest-known-formula-for-the-determinant">Smallest known formula for the determinant</a></p> https://cstheory.stackexchange.com/q/22293 11 Generalizations of the determinant/permanent problem? NisaiVloot https://cstheory.stackexchange.com/users/21714 2014-04-26T14:44:14Z 2014-04-27T15:27:53Z <p>A tantalizing open question in computational complexity is to understand the 'behavioral differences' between the determinant and the permanent. While the former is computable in polynomial time with Gauss pivot, the second is $\# P$-hard by Valiant's result. There have been attempts to generalize the notions of determinant/permanent, but I was wondering if the following notion of <em>subgroup-restricted determinant</em> had been considered.</p> <p>Fix a series $\Sigma$ of subgroups $G_1 \leq G_2 \leq \ldots \leq G_k$ of $S_n$, and for an index $p \leq k$ let $\Sigma_p$ denote the truncated series $G_1 \leq G_2 \leq \ldots \leq G_p$. Say that $\Sigma$ is <em>normal</em> if (i) $G_1$ is simple, (ii) for each $1 \leq i &lt; k$, $G_i$ is a maximal normal subgroup of $G_{i+1}$. We may then define, for an $n \times n$ matrix $A$:</p> <blockquote> <p>Given $K \subseteq S_n$, let $Sum_{K}(A) = \sum_{\sigma \in K} a_{1,\sigma(1)} \ldots a_{n,\sigma(n)}$;</p> <p>Let $SgrDet_{\Sigma}(A) = Sum_{G_k}(A) - \sum_{i = 1}^{k-1} [G_i : G_k] SgrDet_{\Sigma_i}(A)$.</p> </blockquote> <p>Observe that when $G_{k}$ is isomorphic to $Z_n$, any maximal series $\Sigma$ corresponds to a prime factorization of $n = p_1^{i_1} \ldots p_k^{i_k}$, and then $SgrDet_{\Sigma}(I_n)$ corresponds to the 'signed divisor function' $\zeta'(n) = [i_1]_{-p_1} \ldots [i_k]_{-p_k}$ where by convention $[n]_q = \sum_{i = 0}^{n-1} q^i$.</p> <p>Observe that we can recover the permanent and determinant with the series $(S_n)$ and $(A_n \lhd S_n)$, respectively. Note that the second series is normal (by the simplicity of $A_n$) while the first is not. This leads to the following questions, probably difficult:</p> <p>(1) does the formula always have exponential algebraic complexity when the series is not normal?</p> <p>(2) are there other examples of a normal series for which the formula has polynomial complexity?</p> <p>(NOTE: I updated the definition of $SgrDet$ to have a better-behaved operator, but it's still unclear whether it is the 'right' definition).</p> https://cstheory.stackexchange.com/q/27634 10 Implications of Riemann Hypothesis variants in TCS vzn https://cstheory.stackexchange.com/users/7884 2014-11-29T15:52:48Z 2014-11-30T10:11:16Z <p>The over ~1½ century old <a href="http://en.m.wikipedia.org/wiki/Riemann_hypothesis" rel="noreferrer">Riemann Hypothesis</a> 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 reference to a conditional result in TCS based on the Riemann hypothesis. I am therefore wondering,</p> <blockquote> <p>what are the major implications of the Riemann hypothesis in TCS?</p> </blockquote> <p>As a start here is an example from a recent paper, <a href="http://eccc.hpi-web.de/report/2014/163/" rel="noreferrer">Homomorphism Polynomials complete for VP</a> by Durand, Mahajan, Malod, de Rugy-Altherre, and Saurab. From the paper's introduction: </p> <blockquote> <p>One of the most important open questions in algebraic complexity theory is to decide whether the classes VP and VNP are distinct. These classes, first defined by Valiant in [13, 12], are the algebraic analogues of the Boolean complexity classes P and NP, and separating them is essential for separating P from NP (at least non-uniformly and assuming the generalised Riemann Hypothesis, over the field $\mathbb{C}$, ).</p> </blockquote> https://cstheory.stackexchange.com/q/32624 10 Matrix vector multiplication algorithm using minimal number of additions vzn https://cstheory.stackexchange.com/users/7884 2015-09-25T05:59:31Z 2015-09-26T12:42:59Z <p>Consider the following problem:</p> <blockquote> <p>Given a matrix $M$ we want to optimize the number of additions in the multiplication algorithm for computing $v \mapsto Mv$.</p> </blockquote> <p>I find this problem interesting because of its ties with the complexity of matrix multiplication (this problem is a restricted version of matrix multiplication).</p> <p>What is know about this problem?</p> <p>Is there any interesting results relating this problem to the complexity of matrix multiplication problem?</p> <p>The answer to the problem seems to involve finding circuits with only addition gates. What if we allow subtraction gates?</p> <p>I am looking for reductions between this problem and other problems.</p> <hr> <p>Motivated by </p> <ul> <li><a href="https://cs.stackexchange.com/q/45596/">Automated optimization of 0-1 matrix vector multiplication</a> </li> <li><a href="https://cstheory.stackexchange.com/q/32584/">What are the relationships between those hypotheses in Fine-Grained Complexity Theory?</a></li> </ul> https://cstheory.stackexchange.com/q/17501 10 Cancellation and determinant Turbo https://cstheory.stackexchange.com/users/1812 2013-05-03T18:21:12Z 2013-05-10T00:41:40Z <p>Berkowitz algorithm provides a polynomial size circuit with logarithmic depth for determinant of a square matrix using matrix powers. The algorithm implicitly uses cancellation. Is cancellation essential for attaining a circuit of polynomial size with logarithmic or linear depth to calculate determinant (and any possible best circuit for permanent)? Are there fully exponential (not just superpolynomial or sub exponential) lower bounds for these problems using circuits without cancellation?</p> https://cstheory.stackexchange.com/q/14544 10 Why lower bounds for boolean Circuits does not imply arithmetic circuits lower bounds Somebody https://cstheory.stackexchange.com/users/12691 2012-11-30T00:33:53Z 2012-11-30T06:03:04Z <p>My question is why lower bounds for depth 3 Boolean circuits with gates "and" and "xor" for determinant does not imply the same lower bounds for arithmetic circuits over $\mathbb{Z}$?</p> <p>What is wrong with the following argument: Let $C$ be an arithmetic circuit calculating determinant then by taking all variables mod 2 we will get Boolean circuit calculating determinant. </p> https://cstheory.stackexchange.com/q/37310 10 Checking a long product of matrices maomao https://cstheory.stackexchange.com/users/21036 2017-01-16T12:10:24Z 2017-01-16T14:32:03Z <p>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}$. </p> <p>The question is to decide, given $\{A_1, \dots, A_m\}$ and a natural number $k$ <em>in binary</em>, whether there exists a word $w$ over $\{1, \dots, m\}$ whose length is bounded by $k$ such that $[A_w]_{1,1}&gt;0$. </p> <p>This problem is decidable, but its complexity is not clear to me. In particular, is it in PSPACE? (Note that because $k$ is given in binary, one cannot just guess a word $w$ in PSPACE.)</p> https://cstheory.stackexchange.com/q/42438 9 Depth reduction for Boolean circuits Math Learner https://cstheory.stackexchange.com/users/51992 2019-02-25T18:37:24Z 2019-02-27T15:45:01Z <p>This <a href="https://arxiv.org/abs/1304.5777" rel="noreferrer">result</a> by Tavenas, Koiran and others show that any polynomial computed by a circuit of size <span class="math-container">$s$</span> is computed by a depth-4 homogenous circuit of size <span class="math-container">$s^{\sqrt{d}}$</span>.</p> <p>Are there any similar results for Boolean circuits or do we know why such a thing is not possible? </p> https://cstheory.stackexchange.com/q/27139 9 Randomized identity-testing for high degree polynomials? user94741 https://cstheory.stackexchange.com/users/22730 2014-10-21T21:37:47Z 2014-10-23T14:26:16Z <p>Let $f$ be an $n$-variate polynomial given as an arithmetic circuit of size poly$(n)$, and let $p = 2^{\Omega(n)}$ be a prime. </p> <p>Can you test if $f$ is identically zero over $\mathbb{Z}_p$, with time $\mbox{poly}(n)$ and error probability $\leq 1-1/\mbox{poly}(n)$, even if the degree is not a priori bounded? What if $f$ is univariate?</p> <p>Note that you can efficiently test if $f$ is identically zero as a <em>formal</em> <em>expression</em>, by applying Schwartz-Zippel over a field of size say $2^{2|f|}$, because the maximum degree of $f$ is $2^{|f|}$.</p> https://cstheory.stackexchange.com/q/23770 9 Checking if a polynomial factors into linear factors Gorav Jindal https://cstheory.stackexchange.com/users/16008 2014-06-03T14:38:51Z 2014-06-04T14:48:51Z <p>Let $f\in\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ be a polynomial given by an arithmetic circuit $C$ of size $s$. Given $C$ as the input, is there a deterministic algorithm to check whether all the irreducible factors of $f$ in $\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ are linear forms? On a related note, given a linear form $l=\sum_{i=1}^{n}l_{i}\cdot x_{i}$, can we check deterministically whether $l$ is factor of $f$. Of course, we want running time to be polynomial in both the cases. By size, we mean the total bit size. Also, it can be assumed that degree of $f$ is polynomial in $n$.</p> https://cstheory.stackexchange.com/q/16555 8 Is there an alternate proof or an exposition of: Exponential lower bound for $\Sigma\Pi\Sigma$ circuits [Grigoriev-Karpinski(1998)]? Stattrav https://cstheory.stackexchange.com/users/4461 2013-02-19T17:49:46Z 2013-02-20T03:02:55Z <p>Is there an alternate proof or an exposition of the result of Grigoriev and Karpinski (STOC 1998, doi:<a href="http://dx.doi.org/10.1145/276698.276872">10.1145/276698.276872</a>) on the <a href="http://logic.pdmi.ras.ru/~grigorev/pub/determinant_stoc.ps">exponential lower bounds for Depth 3 arithmetic circuits</a> computing $\mathsf{DET}_{n\times n}$ over a fixed finite field?</p> <p>I could not understand section 2 of the paper. What is the intuition behind considering the F-linear operator $T_g$?</p> https://cstheory.stackexchange.com/q/19502 8 Complexity of Polynomial Division SamiD https://cstheory.stackexchange.com/users/214 2013-10-23T20:26:51Z 2014-09-08T14:45:53Z <p>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 are given in unary and the coefficients in binary. What is the complexity of determining $P(x) \bmod{q(x)}$? </p> <p>I am specifically interested in the case when $P(x) = x^N$ for a binary integer $N$ and $q(x)$ is a <em>constant</em> degree polynomial. Any upper bound on this problem will imply the same bound on the <a href="https://cstheory.stackexchange.com/questions/12785/complexity-of-matrix-powering">matrix powering problem</a> (see comment there) for constant size matrices (the degree of $q(x)$ figures as the dimension of the matrix).</p> <p>The problem can be reduced to $\mathsf{BitSLP}$ (see <a href="http://ftp.cs.rutgers.edu/pub/allender/slp.pdf" rel="nofollow noreferrer">this</a> for definition) e.g. by reducing the problem to computing (large) powers of a matrix (<a href="http://alexhealy.net/papers/FieldOps.pdf" rel="nofollow noreferrer">Healy-Viola</a> show how to do the reduction over finite fields in Lemma 21 - the algorithm being essentially the Kung-Sieveking algorithm - but the basic ideas are the same over $\mathbb{Z}$ also. The challenge is to improve the bound from the one for $\mathsf{BitSLP}$ proved in <a href="http://eccc.hpi-web.de/report/2013/177/" rel="nofollow noreferrer">Allender et al</a> viz. $\mathsf{PH}^{\mathsf{PP}^{\mathsf{PP}^\mathsf{PP}}} \subseteq \mathsf{CH}$</p> https://cstheory.stackexchange.com/q/17415 8 Grigoriev-Karpinski for the permanent Ramprasad https://cstheory.stackexchange.com/users/877 2013-04-27T06:56:44Z 2013-04-27T07:01:50Z <p><a href="http://cs.uni-bonn.de/~marek/publications/AELBfD3AC.ps.gz">Grigoriev and Karpinski</a> (ps.Z) showed that any depth-3 circuit over a fixed finite field computing $\mathrm{Det}_n$ requires $2^{\Omega(n)}$ size. I had the misconception(?) until recently that the same proofs also goes through for $\mathrm{Perm}_n$ as well. To add to this, quite a few papers in arithmetic circuit complexity state in passing that the lower bounds is for $\mathrm{Det}_n$ and $\mathrm{Perm}_n$. </p> <p>As far as I can see, the proof technique of Grigoriev and Karpinski when applied to the $\mathrm{Perm}_n$ fails at a subtle technical point. Their proof (for $\mathrm{Det}_n$) uses the following fact: </p> <blockquote> <p>If $X$ is a matrix of indeterminates, and $A$ is an arbitrary matrix, then any minor of $AX$ is a linear combination of minors of $X$.</p> </blockquote> <p>This is not true for the permanent though. For this technical reason, the proof doesn't quite seem to go through. Perhaps there is a simple fix for this that I am missing? Or is this is a really a subtle misconception of a fair number of people?</p> <p>PS: I noticed this only while making a <a href="https://www.dropbox.com/s/6am09xfpnniwu0n/lowerbounds.pdf">consolidated exposition</a> of all known lower bound proofs for myself. The exact place where Grigoriev-Karpinski fails for the $\mathrm{Perm}_n$ is in Lemma 12 of page 7 in the above write-up, or the $T_g$ operator in the original paper. </p> https://cstheory.stackexchange.com/q/41029 7 Reference request: Arithmetic circuit complexity ViX28 https://cstheory.stackexchange.com/users/38266 2018-06-19T12:00:54Z 2020-12-20T10:07:07Z <p>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/video) for a gentle introduction? I found these two given below.</p> <p>Determinant versus permanent by Manindra Agarwal <a href="https://pdfs.semanticscholar.org/6a05/a4fe63e409ba040b890bbf5da0f3b1ca7085.pdf" rel="nofollow noreferrer">https://pdfs.semanticscholar.org/6a05/a4fe63e409ba040b890bbf5da0f3b1ca7085.pdf</a></p> <p>Arithmetic circuits by Amir Shpilka</p> <p><a href="https://www.cs.technion.ac.il/%7Eshpilka/publications/SY10.pdf" rel="nofollow noreferrer">https://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf</a></p> <p><em><strong>Is there any other material which can be more appropriate for a beginner?</strong></em></p> https://cstheory.stackexchange.com/q/38594 7 White-box sparse interpolation Bruno https://cstheory.stackexchange.com/users/976 2017-07-11T08:46:31Z 2017-07-13T09:53:09Z <p>Let $C$ be an <a href="https://en.wikipedia.org/wiki/Arithmetic_circuit_complexity" rel="noreferrer">arithmetic circuit</a> 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 computing $f$ in its sparse representation, given $C$?</p> <p>I am interested in deterministic and randomized complexity, and in the link with <a href="https://en.wikipedia.org/wiki/Polynomial_identity_testing" rel="noreferrer">PIT</a>. In particular, does the promise that $f$ is sparse imply good algorithms? <em>A priori</em>, I am more interested in the case of $\mathbb K$ being some finite field, though results over other fields may be relevant.</p>