8390485
Arithmetic Circuits with Locally Low Algebraic Rank
In recent years, there has been a flurry of activity towards proving lower bounds for homogeneous depth-4 arithmetic circuits, which has brought us very close to statements that are known to imply $\textsf{VP} \neq \textsf{VNP}$. It is open if these techniques can go beyond homogeneity, and in this paper we make some progress in this direction by considering depth-4 circuits of low algebraic rank, which are a natural extension of homogeneous depth-4 circuits. A depth-4 circuit is a representation of an $N$-variate, degree-$n$ polynomial $P$ as \[ P = \sum_{i = 1}^T Q_{i1}\cdot Q_{i2}\cdot \cdots \cdot Q_{it} \; , \] where the $Q_{ij}$ are given by their monomial expansion. Homogeneity adds the constraint that for every $i \in [T]$, $\sum_{j} \operatorname{deg}(Q_{ij}) = n$. We study an extension, where, for every $i \in [T]$, the algebraic rank of the set $\{Q_{i1}, Q_{i2}, \ldots ,Q_{it}\}$ of polynomials is at most some parameter $k$. Already for $k = n$, these circuits are a generalization of the class of homogeneous depth-4 circuits, where in particular $t \leq n$ (and hence $k \leq n$). 
We study lower bounds and polynomial identity tests for such circuits and prove the following results. We show an $\exp{(\Omega(\sqrt{n}\log N))}$ lower bound for such circuits for an explicit $N$ variate degree $n$ polynomial family when $k \leq n$. We also show quasipolynomial hitting sets when the degree of each $Q_{ij}$ and the $k$ are at most $\operatorname{poly}(\log n)$. 
A key technical ingredient of the proofs, which may be of independent interest, is a result which states that over any field of characteristic zero, up to a translation, every polynomial in a set of polynomials can be written as a function of the polynomials in a transcendence basis of the set. We combine this with methods based on shifted partial derivatives to obtain our final results.
47052536
Arithmetic Circuits: A Chasm at Depth Four
We show that proving exponential lower bounds on depth four arithmetic circuits imply exponential lower bounds for unrestricted depth arithmetic circuits. In other words, for exponential sized circuits additional depth beyond four does not help. We then show that a complete black-box derandomization of identity testing problem for depth four circuits with multiplication gates of small fanin implies a nearly complete derandomization of general identity testing.
14339235
Arithmetic circuits: The chasm at depth four gets wider
In their paper on the ''chasm at depth four'', Agrawal and Vinay have shown that polynomials in m variables of degree O(m) which admit arithmetic circuits of size 2^o^(^m^) also admit arithmetic circuits of depth four and size 2^o^(^m^). This theorem shows that for problems such as arithmetic circuit lower bounds or black-box derandomization of identity testing, the case of depth four circuits is in a certain sense the general case. In this paper we show that smaller depth four circuits can be obtained if we start from polynomial size arithmetic circuits. For instance, we show that if the permanent of nxn matrices has circuits of size polynomial in n, then it also has depth 4 circuits of size n^O^(^n^l^o^g^n^). If the original circuit uses only integer constants of polynomial size, then the same is true for the resulting depth four circuit. These results have potential applications to lower bounds and deterministic identity testing, in particular for sums of products of sparse univariate polynomials. We also use our techniques to reprove two results on: -the existence of nontrivial boolean circuits of constant depth for languages in LOGCFL; -reduction to polylogarithmic depth for arithmetic circuits of polynomial size and polynomially bounded degree.
44429162
Improved Bounds for Reduction to Depth 4 and Depth 3
Koiran [7] showed that if an n-variate polynomial of degree d (with d = n O(1)) is computed by a circuit of size s, then it is also computed by a homogeneous circuit of depth four and of size \(2^{O(\sqrt{d}\log(d)\log(s))}\). Using this result, Gupta, Kamath, Kayal and Saptharishi [6] gave an exp \(\left(O\left(\sqrt{d\log(d)\log(n)\log(s)}\right)\right)\) upper bound for the size of the smallest depth three circuit computing an n-variate polynomial of degree d = n O(1) given by a circuit of size s.
2325912
Approaching the Chasm at Depth Four
Agrawal-Vinay [AV08] and Koiran [Koi12] have recently shown that an exp(ω(√n log2 n)) lower bound for depth four homogeneous circuits computing the permanent with bottom layer of × gates having fanin bounded by √n translates to super-polynomial lower bound for general arithmetic circuits computing the permanent. Motivated by this, we examine the complexity of computing the permanent and determinant via such homogeneous depth four circuits with bounded bottom fanin. We show here that any homogeneous depth four arithmetic circuit with bottom fanin bounded by √n computing the permanent (or the determinant) must be of size exp(Ω(√n)).
47308904
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas
We show here a $2^{\Omega(\sqrt{d} \cdot \log N)}$ size lower bound for homogeneous depth four arithmetic formulas over fields of characteristic zero. That is, we give an explicit family of polynomials of degree $d$ on $N$ variables (with $N = d^3$ in our case) with 0, 1-coefficients such that for any representation of a polynomial $f$ in this family of the form $ f = \sum_{i} \prod_{j} Q_{ij}, $ where the $Q_{ij}$'s are homogeneous polynomials (recall that a polynomial is said to be homogeneous if all its monomials have the same degree), it must hold that $ \sum_{i, j} (\text{number of monomials of~} Q_{ij}) \geq 2^{\Omega (\sqrt{d} \cdot \log N)}. $ The abovementioned family, which we refer to as the Nisan--Wigderson design-based family of polynomials, is in the complexity class $\mathsf{VNP}$. Our work builds on recent lower bound results and yields an improved quantitative bound as compared to the quasi-polynomial lower bound of [N. Kayal et al., in Symposium on Theory of Computing, ACM, New York, 201...
17294708
An exponential lower bound for the sum of powers of bounded degree polynomials
In this work we consider representations of multivariate polynomials in F[x] of the form f(x) = Q1(x) +Q2(x) + . . .+Qs(x) , where the ei’s are positive integers and the Qi’s are arbitary multivariate polynomials of bounded degree. We give an explicit n-variate polynomial f of degree n such that any representation of the above form for f requires the number of summands s to be 2. Motivation. Let F be a field, F[x] be the set of n-variate polynomials over F and d ≥ 1 be an integer. For a polynomial f(x) ∈ F[x], we consider representations of the form f(x) = Q1 1 (x) +Q e2 2 (x) + . . .+Q es s (x), (1) where the Qi(x)’s are polynomials of degree at most d. We do this with an eye towards proving lower bounds for the number of summands s required to write some explicit polynomial f in the above form. Our motivation for this line of inquiry stems from some recent results and problems posed in the field of arithmetic complexity. Agrawal and Vinay [AV08] showed that proving exponential lower bounds for depth four arithmetic circuits implies exponential lower bounds for arbitrary depth arithmetic circuits. In our case, a representation of the form (1) above corresponds to computing f via a depth four ΣΠΣΠ arithmetic circuit where the bottommost layer of multiplication gates have fanin bounded by d and the second-last layer of multiplication gates actually consists of exponentiation gates of arbitrarily large degree (i.e. multiplication gates where all the incoming edges originate from a single node). Meanwhile Hrubes, Wigderson and Yehudayoff [HWY10] look at the situation where d = e1 = e2 = . . . = es = 2 and ask for a superlinear lower bound on the number of summands s for an explicit n-variate biquadratic polynomial f . They show that such a superlinear lower bound implies an exponential lower bound on the size of arithmetic circuits computing the noncommutative permanent. Finally Chen, Kayal and Wigderson [CKW11] pose the problem of proving lower bounds for bounded depth arithmetic circuits with addition and exponentiation gates. Our main theorem is a lower bound on the number of summands in any representation of the form (1) for an explicit polynomial. Theorem 1. (Lower bound for sum of powers). Let F be any field and F[x] be the ring of polynomials over the set of indeterminates x = (x1, x2, . . . , xn). Let e1, e2, . . . , es be positive integers and Q1, Q2, . . . , Qs ∈ F[x] be multivariate polynomials each of degree at most d. If Q1 1 +Q e2 2 + . . .+Q es s = (x1 · x2 · . . . · xn), then we must have that (log s) = Ω( n 2d ). In particular, if d is a constant then s = 2Ω(n). Remark 2. 1. The fact that the f in the lower bound above consists of a single monomial indicates above all the severe limitation of representations of the form (1). ∗Microsoft Research India, neeraka@microsoft.com 1 ISSN 1433-8092 Electronic Colloquium on Computational Complexity, Report No. 81 (2012) 2. An upper bound of 2n/d is an easy corollary of Fischer [Fis94]. Specifically, let F be an algebraically closed field with char(F) > n. Then for all integers d ≥ 1 there exist polynomials Q1, Q2, . . . , Qs each of degree d such that Q1 1 +Q e2 2 + . . .+Q es s = (x1 · x2 · . . . · xn), and the number of summands s is at most 2n/d. Fischer [Fis94] gives an explicit set of 2m−1 linear forms `1, `2, . . . , `2m such that (y1 · y2 · . . . · ym) = ∑
2936471
Depth-3 arithmetic circuits over fields of characteristic zero
Abstract. In this paper we prove quadratic lower bounds for depth-3 arithmetic circuits over fields of characteristic zero. Such bounds are obtained for the elementary symmetric functions, the (trace of) iterated matrix multiplication, and the determinant. As corollaries we get the first nontrivial lower bounds for computing polynomials of constant degree, and a gap between the power of depth-3 arithmetic circuits and depth-4 arithmetic circuits. We also give new shorter formulae of constant depth for the elementary symmetric functions.¶The main technical contribution relates the complexity of computing a polynomial in this model to the wealth of partial derivatives it has on every affine subspace of small co-dimension. Lower bounds for related models utilize an algebraic analog of the Neciporuk lower bound on Boolean formulae.
7790115
Affine projections of symmetric polynomials
We introduce a new model for computing polynomials-a depth 2 circuit with a symmetric gate at the top and plus gates at the bottom, i.e. the circuit computes a symmetric function in linear functions-S/sub m//sup d/(l/sub 1/, l/sub 2/, ..., l/sub m/) (S/sub m//sup d/ is the d'th elementary symmetric polynomial in m variables, and the l/sub i/'s are linear functions). We refer to this model as the symmetric model. This new model is related to standard models of arithmetic circuits, especially to depth 3 circuits. In particular we show that, in order to improve the results of Shpilka and Wigderson (1999), i.e. to prove super-quadratic lower bounds for depth 3 circuits, one must first prove a super-linear lower bound for the symmetric model. We prove two nontrivial linear lower bounds for our model. The first lower bound is for computing the determinant, and the second is for computing the sum of two monomials. The main technical contribution relates the maximal dimension of linear subspaces on which S/sub m//sup d/ vanishes, and lower bounds to the symmetric model. In particular we show that an answer of the following problem (which is very natural, and of independent interest) will imply lower bounds on symmetric circuits for many polynomials: "what is the maximal dimension of a linear subspace of C/sup m/, on which S/sub m//sup d/ vanishes?" We give two partial solutions to the problem above, each enables us to prove a different lower bound.
11057381
An almost Cubic Lower Bound for Depth Three Arithmetic Circuits
We show an almost cubic lower bound on the size of any depth three arithmetic circuit computing an explicit multilinear polynomial in n variables over any field. This improves upon the previously known quadratic lower bound by Shpilka and Wigderson [CCC, 1999].
11724752
Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits
In this work we study two, seemingly unrelated, notions. Locally Decodable Codes (LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial Identity Testing (PIT) is one of the fundamental problems of algebraic complexity: we are given a circuit computing a multivariate polynomial and we have to determine whether the polynomial is identically zero. We improve known results on locally decodable codes and on polynomial identity testing and show a relation between the two notions. In particular we obtain the following results:We show that if E: Fn → Fm is a linear LDC with 2 queries then m = exp(Ω(n)). Previously this was only known for fields of size << 2n [18].We show that from every depth 3 arithmetic circuit (ΣΠΣ circuit), C, with a bounded (constant) top fan-in that computes the zero polynomial, one can construct a locally decodeable code. More formally: Assume that C is minimal (no subset of the multiplication gates sums to zero) and simple (no linear function appears in all the multiplication gates). Denote by d the degree of the polynomial computed by C and by r the rank of the linear functions appearing in C. Then we can construct a linear LDC with 2 queries, that encodes messages of length r/polylog(d) by codewords of length O(d).We prove a structural theorem for ΣΠΣ circuits, with a bounded top fan-in, that compute the zero polynomial. In particular we show that if such a circuit is simple and minimal and of polynomial size then its rank, r, is only polylogarithmic in the number of variables (a priory it could have been linear).We give new PIT algorithms for ΣΠΣ circuits with a bounded top fan-in:A deterministic algorithm that runs in quasi polynomial time.A randomized algorithm that runs in polynomial time and uses only polylogarithmic number of random bits..Moreover, when the circuit is multilinear our deterministic algorithm runs in polynomial time. Previously, deterministic subexponential time algorithms for PIT in bounded depth circuits were known only for depth 2 circuits (in the black box model)[22, 9, 28]. In particular, for the special case of depth 3 circuits with 3 multiplication gates our result resolves an open question asked by Klivans and Spielman [28].
2589671
Polynomial Identity Testing for Depth 3 Circuits
Abstract.We study the identity testing problem for depth 3 arithmetic circuits (
$$\sum\prod\sum$$
 circuit). We give the first deterministic polynomial time identity test for 
$$\sum\prod\sum$$
 circuits with bounded top fanin. We also show that the rank of a minimal and simple 
$$\sum\prod\sum$$
 circuit with bounded top fanin, computing zero, can be unbounded. These results answer the open questions posed by Klivans–Spielman (STOC 2001) and Dvir–Shpilka (STOC 2005).
28246163
Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in
AbstractIn this paper we consider the problem of determining whether an unknown arithmetic circuit, for which we have oracle access, computes the identically zero polynomial. This problem is known as the black-box polynomial identity testing (PIT) problem. Our focus is on polynomials that can be written in the form $f(\bar x) = \sum\nolimits_{i = 1}^k {h_i (\bar x) \cdot g_i (\bar x)} $, where each hi is a polynomial that depends on only ρ linear functions, and each gi is a product of linear functions (when hi = 1, for each i, then we get the class of depth-3 circuits with k multiplication gates, also known as ΣΠΣ(k) circuits, but the general case is much richer). When maxi(deg(hi · gi)) = d we say that f is computable by a ΣΠΣ(k; d;ρ) circuit. We obtain the following results.
1.A deterministic black-box identity testing algorithm for ΣΠΣ(k; d;ρ) circuits that runs in quasi-polynomial time (for ρ=polylog(n+d)). In particular this gives the first black-box quasi-polynomial time PIT algorithm for depth-3 circuits with k multiplication gates.2.A deterministic black-box identity testing algorithm for read-k ΣΠΣ circuits (depth-3 circuits where each variable appears at most k times) that runs in time $n^{2^{O(k^2 )} } $. In particular this gives a polynomial time algorithm for k=O(1).
 Our results give the first sub-exponential black-box PIT algorithm for circuits of depth higher than 2. Another way of stating our results is in terms of test sets for the underlying circuit model. A test set is a set of points such that if two circuits get the same values on every point of the set then they compute the same polynomial. Thus, our first result gives an explicit test set, of quasi-polynomial size, for ΣΠΣ(k; d;ρ) circuits (when ρ=polylog(n+d)). Our second result gives an explicit polynomial size test set for read-k depth-3 circuits.The proof technique involves a construction of a family of affine subspaces that have a rank-preserving property that is inspired by the construction of linear seeded extractors for affine sources of Gabizon and Raz [9], and a generalization of a theorem of [8] regarding the structure of identically zero depth-3 circuits with bounded top fan-in.
2559859
Blackbox Polynomial Identity Testing for Depth 3 Circuits
We study depth three arithmetic circuits with bounded top fanin. We give the first deterministic polynomial time blackbox identity test for depth three circuits with bounded top fanin over the field of rational numbers, thus resolving a question posed by Klivans and Spielman (STOC 2001). Our main technical result is a structural theorem for depth three circuits with bounded top fanin that compute the zero polynomial. In particular we show that if a circuit C with real coefficients is simple, minimal and computes the zero polynomial, then the rank of C can be upper bounded by a function only of the top fanin. This proves a weak form of a conjecture of Dvir and Shpilka (STOC 2005) on the structure of identically zero depth three arithmetic circuits. Our blackbox identity test follows from this structural theorem by combining it with a construction of Karnin and Shpilka (CCC 2008). Our proof of the structure theorem exploits the geometry of finite point sets in R^n. We identify the linear forms appearing in the circuit C with points in R^n. We then show how to apply high dimensional versions of the Sylvester--Gallai Theorem, a theorem from incidence-geometry, to identify a special linear form appearing in C, such that on the subspace where the linear form vanishes, C restricts to a simpler circuit computing the zero polynomial. This allows us to build an inductive argument bounding the rank of our circuit. While the utility of such theorems from incidence geometry for identity testing has been hinted at before, our proof is the first to develop the connection fully and utilize it effectively.
17382908
Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in
We give the first sub-exponential time deterministic polynomial identity testing algorithm for depth-4 multilinear circuits with a small top fan-in. More accurately, our algorithm works for depth-4 circuits with a plus gate at the top (also known as ΣΠΣΠ circuits) and has a running time of exp(poly(log(n),log(s),k)) where n is the number of variables, s is the size of the circuit and k is the fan-in of the top gate. In particular, when the circuit is of polynomial (or quasi-polynomial) size, our algorithm runs in quasi-polynomial time. In [AV08], it was shown that derandomizing polynomial identity testing for general ΣΠΣΠ circuits implies a derandomization of polynomial identity testing in general arithmetic circuits. Prior to this work sub-exponential time deterministic algorithms were known for depth-$3$ circuits with small top fan-in and for very restricted versions of depth-4 circuits.
 The main ingredient in our proof is a new structural theorem for multilinear ΣΠΣΠ(k) circuits. Roughly, this theorem shows that any nonzero multilinear ΣΠΣΠ(k) circuit contains an `embedded' nonzero multilinear ΣΠΣ(k) circuit. Using ideas from previous works on identity testing of sums of read-once formulas and of depth-3 multilinear circuits, we are able to exploit this structure and obtain an identity testing algorithm for multilinear ΣΠΣΠ(k) circuits.
126248747
From Sylvester-Gallai Configurations to Rank Bounds: Improved Black-Box Identity Test for Depth-3 Circuits
We study the problem of identity testing for depth-3 circuits of top fanin k and degree d. We give a new structure theorem for such identities. A direct application of our theorem improves the known deterministic d^{k^k}-time black-box identity test over rationals (Kayal & Saraf, FOCS 2009) to one that takes d^{k^2}-time. Our structure theorem essentially says that the number of independent variables in a real depth-3 identity is very small. This theorem affirmatively settles the strong rank conjecture posed by Dvir & Shpilka (STOC 2005). We devise a powerful algebraic framework and develop tools to study depth-3 identities. We use these tools to show that any depth-3 identity contains a much smaller nucleus identity that contains most of the "complexity" of the main identity. The special properties of this nucleus allow us to get almost optimal rank bounds for depth-3 identities.
3091931
Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter
Let C be a depth-3 circuit with n variables, degree d and top fanin k (called ΣΠΣ(k,d,n) circuits) over base field FF. It is a major open problem to design a deterministic polynomial time blackbox algorithm that tests if C is identically zero. Klivans & Spielman (STOC 2001) observed that the problem is open even when k is a constant. This case has been subjected to a serious study over the past few years, starting from the work of Dvir & Shpilka (STOC 2005).
 We give the first polynomial time blackbox algorithm for this problem. Our algorithm runs in time poly(n)dk, regardless of the base field. The only field for which polynomial time algorithms were previously known is FF = QQ (Kayal & Saraf, FOCS 2009, and Saxena & Seshadhri, FOCS 2010). This is the first blackbox algorithm for depth-$3$ circuits that does not use the rank based approaches of Karnin & Shpilka (CCC 2008).
 We prove an important tool for the study of depth-3 identities. We design a blackbox polynomial time transformation that reduces the number of variables in a ΣΠΣ(k,d,n) circuit to k variables, but preserves the identity structure.
15795194
Black-box identity testing of depth-4 multilinear circuits
We study the problem of identity testing for multilinear ΣΠΣΠ(k) circuits, i.e. multilinear depth-4 circuits with fan-in k at the top + gate. We give the first polynomial-time deterministic identity testing algorithm for such circuits. Our results also hold in the black-box setting.
 The running time of our algorithm is (ns)O(k3), where n is the number of variables, s is the size of the circuit and k is the fan-in of the top gate. The importance of this model arises from [3], where it was shown that derandomizing black-box polynomial identity testing for general depth-4 circuits implies a derandomization of polynomial identity testing (PIT) for general arithmetic circuits. Prior to our work, the best PIT algorithm for multilinear ΣΠΣΠ(k) circuits [13] ran in quasi-polynomial-time, with the running time being nO(k6 log(k) log2 s ).
 We obtain our results by showing a strong structural result for multilinear ΣΠΣΠ(k) circuits that compute the zero polynomial. We show that under some mild technical conditions, any gate of such a circuit must compute a sparse polynomial. We then show how to combine the structure theorem with a result by Klivans and Spielman [17], on the identity testing for sparse polynomials, to yield the full result.
22501458
Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-D Occur-k Formulas and Depth-3 Transcendence Degree-k Circuits
We present a single common tool to strictly subsume all known cases of polynomial time black box polynomial identity testing (PIT), that have been hitherto solved using diverse tools and techniques, over fields of zero or large characteristic. In particular, we show that polynomial (in the size of the circuit) time hitting-set generators for identity testing of the two seemingly different and well studied models---depth-3 circuits with bounded top fanin, and constant-depth constant-read multilinear formulas---can be constructed using one common algebraic-geometry theme: Jacobian captures algebraic independence. By exploiting the Jacobian, we design the first efficient hitting-set generators for broad generalizations of the above-mentioned models, namely, (a) depth-3 ($\Sigma \Pi \Sigma$) circuits with constant transcendence degree of the polynomials computed by the product gates (no bounded top fanin restriction), and (b) constant-depth constant-occur formulas (no multilinear restriction). Constant occur ...
2808994
Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs
We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing algorithms (PIT) for algebraic branching programs (ABPs) that are read-once and oblivious. This class has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka), but prior to this work there was no known such black-box algorithm. The main result of this work gives the first quasi-polynomial sized hitting sets for size S circuits from this class, when the order of the variables is known. As our hitting set is of size exp(lg2 S), this is analogous (in the terminology of boolean pseudorandom ness) to a seed-length of lg2 S, which is the seed length of the pseudorandom generators of Nisan and Impagliazzo-Nisan-Wigderson for read-once oblivious boolean branching programs. Thus our work can be seen as an algebraic analogue of these foundational results in boolean pseudorandom ness. Our results are stronger for branching programs of bounded width, where we give a hitting set of size exp(lg2 S/lglg S), corresponding to a seed length of lg2 S/lglg S. This is in stark contrast to the known results for read-once oblivious boolean branching programs of bounded width, where no pseudorandom generator (or hitting set) with seed length o(lg2 S) is known. Thus, while our work is in some sense an algebraic analogue of existing boolean results, the two regimes seem to have non-trivial differences. In follow up work, we strengthened a result of Mulmuley, and showed that derandomizing a particular case of the No ether Normalization Lemma is reducible to black-box PIT of read-once oblivious ABPs. Using the results of the present work, this gives a derandomization of No ether Normalization in that case, which Mulmuley conjectured would difficult due to its relations to problems in algebraic geometry. We also show that several other circuit classes can be black-box reduced to read-once oblivious ABPs, including set-multilinear ABPs (a generalization of depth-3 set-multilinear formulas), non-commutative ABPs (generalizing non-commutative formulas), and (semi-)diagonal depth-4 circuits (as introduced by Saxena). For set-multilinear ABPs and non-commutative ABPs, we give quasi-polynomial-time black-box PIT algorithms, where the latter case involves evaluations over the algebra of (D+1)x(D+1) matrices, where D is the depth of the ABP. For (semi-)diagonal depth-4 circuits, we obtain a black-box PIT algorithm (over any characteristic) whose run-time is quasi-polynomial in the runtime of Saxena's white-box algorithm, matching the concurrent work of Agrawal, Saha, and Saxena. Finally, by combining our results with the reconstruction algorithm of Klivans and Shpilka, we obtain deterministic reconstruction algorithms for the above circuit classes.
1157184
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas
In this paper, we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds, we obtain lower bounds for these models.For depth-3 multilinear formulas, of size exp$${(n^\delta)}$$(nδ), we give a hitting set of size exp$${\left(\tilde{O}\left(n^{2/3 + 2\delta/3}\right) \right)}$$O~n2/3+2δ/3. This implies a lower bound of exp$${(\tilde{\Omega}(n^{1/2}))}$$(Ω~(n1/2)) for depth-3 multilinear formulas, for some explicit polynomial.For depth-4 multilinear formulas, of size exp$${(n^\delta)}$$(nδ), we give a hitting set of size exp$${\left(\tilde{O}\left(n^{2/3 + 4\delta/3}\right) \right)}$$O~n2/3+4δ/3. This implies a lower bound of exp$${(\tilde{\Omega}(n^{1/4}))}$$(Ω~(n1/4)) for depth-4 multilinear formulas, for some explicit polynomial.A regular formula consists of alternating layers of $${+,\times}$$+,× gates, where all gates at layer i have the same fan-in. We give a hitting set of size (roughly) exp$${\left(n^{1- \delta}\right)}$$n1-δ, for regular depth-d multilinear formulas with formal degree at most n and size exp$${(n^\delta)}$$(nδ), where $${\delta = O(1/{\sqrt{5}^d})}$$δ=O(1/5d). This result implies a lower bound of roughly exp$${(\tilde{\Omega}(n^{1/{\sqrt{5}^d}}))}$$(Ω~(n1/5d)) for such formulas.We note that better lower bounds are known for these models, but also that none of these bounds was achieved via construction of a hitting set. Moreover, no lower bound that implies such PIT results, even in the white-box model, is currently known.Our results are combinatorial in nature and rely on reducing the underlying formula, first to a depth-4 formula, and then to a read-once algebraic branching program (from depth-3 formulas, we go straight to read-once algebraic branching programs).
11366071
Algebraic Independence and Blackbox Identity Testing
Algebraic independence is an advanced notion in commutative algebra that generalizes independence of linear polynomials to higher degree. The transcendence degree (trdeg) of a set {f1, ..., fm} ⊂ F[x1, ..., xn] of polynomials is the maximal size r of an algebraically independent subset. In this paper we design blackbox and efficient linear maps ϕ that reduce the number of variables from n to r but maintain trdeg{ϕ(fi)}i = r, assuming fi's sparse and small r. We apply these fundamental maps to solve several cases of blackbox identity testing: 1. Given a circuit C and sparse subcircuits f1, ..., fm of trdeg r such that D := C(f1, ..., fm) has polynomial degree, we can test blackbox D for zeroness in poly(size(D))r time. 2. Define a ΣΠΣΠδ(k, s, n) circuit C to be of the form Σi=1k Πj=1s fi,j, where fi,j are sparse n-variate polynomials of degree at most δ. For k = 2, we give a poly (δsn)δ2 time blackbox identity test. 3. For a general depth-4 circuit we define a notion of rank. Assuming there is a rank bound R for minimal simple ΣΠΣΠδ(k, s, n) identities, we give a poly(δsnR)Rkδ2 time blackbox identity test for ΣΠΣΠδ(k, s, n) circuits. This partially generalizes the state of the art of depth-3 to depth-4 circuits. 
 
The notion of trdeg works best with large or zero characteristic, but we also give versions of our results for arbitrary fields.
2489796
An exponential lower bound for depth 3 arithmetic circuits
We prove the rst exponential lower bound on the size of any depth 3 arithmetic circuit with unbounded fanin computing an explicit function (the determinant) over an arbitrary nite eld. This answers an open problem of N91] and NW95] for the case of nite elds. We intepret here arithmetic circuits in the algebra of polynomials over the given eld. The proof method involves a new argument on the rank of linear functions, and a group symmetry on polynomials vanishing at certain nonsingular matrices, and could be of independent interest.
26189857
Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields
Abstract. A depth 3 arithmetic circuit can be viewed as a sum of products of linear functions. We prove an exponential complexity lower bound on depth 3 arithmetic circuits computing some natural symmetric functions over a finite field F. Also, we study the complexity of the functions f : Dn→F for subsets D⊂F. In particular, we prove an exponential lower bound on the complexity of depth 3 arithmetic circuits computing some explicit functions f:(F*)n→F (in particular, the determinant of a matrix).
17311113
A Probabilistic Remark on Algebraic Program Testing
Abstract : A key step in Howden's method for algebraic program testing requires checking the algebraic identity of multinomials. Howden's solution requires evaluations in at least 2 to the mth power points for m-ary multinomials. This note presents a probabilistic solution which achieves small probability of error on 30 points.
3051558
Deterministic Divisibility Testing via Shifted Partial Derivatives
Kayal has recently introduced the method of shifted partial derivatives as a way to give the first exponential lower bound for computing an explicit polynomial as a sum of powers of constant-degree polynomials. This method has garnered further attention because of the work of Gupta, Kamath, Kayal and Saptharishi who used this method to obtain lower bounds that approach the "chasm at depth-4". In this work, we investigate to what extent this method can be used to obtain deterministic polynomial identity testing (PIT) algorithms, which are algorithms that decide whether a given algebraic circuit computes the zero polynomial. In particular, we give a poly(s)(log s)-time deterministic black-box PIT algorithm for a size-s sum of powers of constant-degree polynomials. This is the first sub-exponential deterministic PIT algorithm for this model of computation and the first PIT algorithm based on the method of shifted partial derivatives. We also study the problem of divisibility testing, which when given multivariate polynomials f and g (as algebraic circuits) asks to decide whether f divides g. Using Strassen's technique for the elimination of divisions, we show that one can obtain deterministic divisibility testing algorithms via deterministic PIT algorithms, and this reduction does not dramatically increase the complexity of the underlying algebraic circuits. Using this reduction, we show that deciding divisibility of a constant-degree polynomial f into a sparse polynomial g reduces to PIT of sums of a monomial multiplied by a power of constant-degree polynomials. We then extend the method of shifted partial derivatives to give a poly(s)(log s)-time deterministic black-box PIT algorithm for this model of computation, and thus derive a corresponding deterministic divisibility algorithm. This is the first non-trivial deterministic algorithm for this problem. Previous work on multivariate divisibility testing due to Saha, Saptharishi and Saxena gave algorithms for when f is linear and g is sparse, and essentially worked via PIT algorithms for read-once (oblivious) algebraic branching programs (roABPs). We give explicit sums of powers of quadratic polynomials that require exponentially-large roABPs in a strong sense, showing that techniques known for roABPs have limited applicability in our regime. Finally, by combining our results with the algorithm of Forbes, Shpilka and Saptharishi we obtain poly(s)(log log s)-time deterministic black-box PIT algorithms for various models (translations of sparse polynomials, and sums of monomials multiplied by a power of a linear polynomial) where only poly(s) (Theta(log s))-time such algorithms were previously known.
8900370
Extractors And Rank Extractors For Polynomial Sources
Abstract.In this paper we construct explicit deterministic extractors from polynomial sources, which are distributions sampled by low degree multivariate polynomials over finite fields. This naturally generalizes previous work on extraction from affine sources (which are degree 1 polynomials). A direct consequence is a deterministic extractor for distributions sampled by polynomial size arithmetic circuits over exponentially large fields. The steps in our extractor construction, and the tools (mainly from algebraic geometry) that we use for them, are of independent interest:The first step is a construction of rank extractors, which are polynomial mappings which ‘extract’ the algebraic rank from any system of low degree polynomials. More precisely, for any n polynomials, k of which are algebraically independent, a rank extractor outputs k algebraically independent polynomials of slightly higher degree. The rank extractors we construct are applicable not only over finite fields but also over fields of characteristic zero.The next step is relating algebraic independence to min-entropy. We use a theorem of Wooley to show that these parameters are tightly connected. This allows replacing the algebraic assumption on the source (above) by the natural information theoretic one. It also shows that a rank extractor is already a high quality condenser for polynomial sources over polynomially large fields.Finally, to turn the condensers into extractors, we employ a theorem of Bombieri, giving a character sum estimate for polynomials defined over curves. It allows extracting all the randomness (up to a multiplicative constant) from polynomial sources over exponentially large prime fields.
1251271
Hardness-randomness tradeoffs for bounded depth arithmetic circuits
In this paper we show that lower bounds for bounded depth arithmetic circuits imply derandomization of polynomial identity testing for bounded depth arithmetic circuits. More formally, if there exists an explicit polynomial f(x1,...,xm) that cannot be computed by a depth d arithmetic circuit of small size then there exists an efficient deterministic algorithm to test whether a given depth d-8 circuit is identically zero or not (assuming the individual degrees of the tested circuit are not too high). In particular, if we are guaranteed that the circuit computes a multilinear polynomial then we can perform the identity test efficiently. To the best of our knowledge this is the first hardness-randomness tradeoff for bounded depth arithmetic circuits. The above results are obtained using the arithmetic Nisan-Wigderson generator of Impagliazzo and Kabanets together with a new theorem on bounded depth circuits, which is the main technical contribution of our work. This theorem deals with polynomial equations of the form P(x1,...,xn,y) ≡ 0 and shows that if P has a circuit of depth d and size s and if the polynomial f(x1,...,xn) satisfies P(x1,...,xn,f(x1,...,xn))≡ 0 then f has a circuit of depth d+3 and size O(s • r + mr), where m is the degree of f and r is the highest degree of the variable y appearing in P. In the other direction we observe that the methods of Impagliazzo and Kabanets imply that if we can derandomize polynomial identity testing for bounded depth circuits then NEXP does not have bounded depth arithmetic circuits. That is, either NEXP ⊄ P/poly or the Permanent is not computable by polynomial size bounded depth arithmetic circuits.
52073960
Algebraic Independence over Positive Characteristic: New Criterion and Applications to Locally Low Algebraic Rank Circuits
The motivation for this work comes from two problems--test algebraic independence of arithmetic circuits over a field of small characteristic, and generalize the structural property of algebraic dependence used by (Kumar, Saraf CCC'16) to arbitrary fields. 
It is known that in the case of zero, or large characteristic, using a classical criterion based on the Jacobian, we get a randomized poly-time algorithm to test algebraic independence. Over small characteristic, the Jacobian criterion fails and there is no subexponential time algorithm known. This problem could well be conjectured to be in RP, but the current best algorithm puts it in NP^#P (Mittmann, Saxena, Scheiblechner Trans.AMS'14). Currently, even the case of two bivariate circuits over F_2 is open. We come up with a natural generalization of Jacobian criterion, that works over all characteristic. The new criterion is efficient if the underlying inseparable degree is promised to be a constant. This is a modest step towards the open question of fast independence testing, over finite fields, posed in (Dvir, Gabizon, Wigderson FOCS'07). 
 
In a set of linearly dependent polynomials, any polynomial can be written as a linear combination of the polynomials forming a basis. The analogous property for algebraic dependence is false, but a property approximately in that spirit is named as ``functional dependence'' in (Kumar, Saraf CCC'16) and proved for zero or large characteristic. We show that functional dependence holds for arbitrary fields, thereby answering the open questions in (Kumar, Saraf CCC'16). Following them we use the functional dependence lemma to prove the first exponential lower bound for locally low algebraic rank circuits for arbitrary fields (a model that strongly generalizes homogeneous depth-4 circuits). We also recover their quasipoly-time hitting-set for such models, for fields of characteristic smaller than the ones known before. 
 
Our results show that approximate functional dependence is indeed a more fundamental concept than the Jacobian as it is field independent. We achieve the former by first picking a ``good'' transcendence basis, then translating the circuits by new variables, and finally approximating them by truncating higher degree monomials. We give a tight analysis of the ``degree'' of approximation needed in the criterion. To get the locally low algebraic rank circuit applications we follow the known shifted partial derivative based methods.
53034766
Read-once polynomial identity testing
In this paper we study the problems of polynomial identity testing (PIT) and reconstruction of read-once formulas. The following are some deterministic algorithms that we obtain. An nO(k2) algorithm for checking whether given k ROFs sum to zero or not. An nO(d+k2) time algorithm for checking whether a black box holding the sum of k depth d ROFs computes the zero polynomial. In other words, we provide a hitting set of size nO(d+k2) for the sum of k depth d ROFs. This implies an nO(d) deterministic algorithm for the reconstruction of depth d ROFs. A hitting set of size exp(~O(√n+k2)) for the sum of k ROFs (without depth restrictions). This implies a sub-exponential time deterministic algorithm for black-box identity testing and reconstructing of ROFs. To the best of our knowledge our results give the first polynomial time (non black-box) and sub-exponential time (black-box) identity testing algorithms for the sum of (a constant number of) ROFs. In addition, we introduce and study the read-once testing problem (ROT for short): Given an arithmetic circuit computing a polynomial P(x), decide whether there is a ROF computing P(x). If there is such a formula then output it. Otherwise output "No". We show that most previous algorithms for polynomial identity testing can be strengthen to yield algorithms for the ROT problem. In particular we give ROT algorithms for: Depth-2 circuits (circuits computing sparse polynomials), Depth-3 circuits with bounded top fan-in (both in the black-box and non black-box settings, where the running time depends on the model), non-commutative formulas and sum of k ROFs. The running time of the ROT algorithm is essentially the same running time as the corresponding PIT algorithm for the class. The main tool in most of our results is a new connection between polynomial identity testing and reconstruction of read-once formulas. Namely, we show that in any model that is closed under partial derivatives (that is, a partial derivative of a polynomial computed by a circuit in the model, can also be computed by a circuit in the model) and that has an efficient deterministic polynomial identity testing algorithm, we can also answer the read-once testing problem.
10291925
Sums of products of polynomials in few variables : lower bounds and polynomial identity testing
We study the complexity of representing polynomials as a sum of products of polynomials in few variables. More precisely, we study representations of the form $$P = \sum_{i = 1}^T \prod_{j = 1}^d Q_{ij}$$ such that each $Q_{ij}$ is an arbitrary polynomial that depends on at most $s$ variables. We prove the following results. 
1. Over fields of characteristic zero, for every constant $\mu$ such that $0 \leq \mu < 1$, we give an explicit family of polynomials $\{P_{N}\}$, where $P_{N}$ is of degree $n$ in $N = n^{O(1)}$ variables, such that any representation of the above type for $P_{N}$ with $s = N^{\mu}$ requires $Td \geq n^{\Omega(\sqrt{n})}$. This strengthens a recent result of Kayal and Saha [KS14a] which showed similar lower bounds for the model of sums of products of linear forms in few variables. It is known that any asymptotic improvement in the exponent of the lower bounds (even for $s = \sqrt{n}$) would separate VP and VNP[KS14a]. 
2. We obtain a deterministic subexponential time blackbox polynomial identity testing (PIT) algorithm for circuits computed by the above model when $T$ and the individual degree of each variable in $P$ are at most $\log^{O(1)} N$ and $s \leq N^{\mu}$ for any constant $\mu < 1/2$. We get quasipolynomial running time when $s < \log^{O(1)} N$. The PIT algorithm is obtained by combining our lower bounds with the hardness-randomness tradeoffs developed in [DSY09, KI04]. To the best of our knowledge, this is the first nontrivial PIT algorithm for this model (even for the case $s=2$), and the first nontrivial PIT algorithm obtained from lower bounds for small depth circuits.
1852313
A super-polynomial lower bound for regular arithmetic formulas
We consider arithmetic formulas consisting of alternating layers of addition (+) and multiplication (×) gates such that the fanin of all the gates in any fixed layer is the same. Such a formula Φ which additionally has the property that its formal/syntactic degree is at most twice the (total) degree of its output polynomial, we refer to as a regular formula. As usual, we allow arbitrary constants from the underlying field F on the incoming edges to a + gate so that a + gate can in fact compute an arbitrary F-linear combination of its inputs. We show that there is an (n2 + 1)-variate polynomial of degree 2n in VNP such that any regular formula computing it must be of size at least nΩ(log n). Along the way, we examine depth four (ΣΠΣΠ) regular formulas wherein all multiplication gates in the layer adjacent to the inputs have fanin a and all multiplication gates in the layer adjacent to the output node have fanin b. We refer to such formulas as ΣΠ[b]ΣΠ[a]-formulas. We show that there exists an n2-variate polynomial of degree n in VNP such that any ΣΠ[O(√n)]ΣΠ[√n]-formula computing it must have top fan-in at least 2Ω(√n·log n). In comparison, Tavenas [Tav13] has recently shown that every nO(1)-variate polynomial of degree n in VP admits a ΣΠ[O(√n)]ΣΠ[√n]-formula of top fan-in 2O(√n·log n). This means that any further asymptotic improvement in our lower bound for such formulas (to say 2ω(√n log n)) will imply that VP is different from VNP.
1775917
An exponential lower bound for homogeneous depth-5 circuits over finite fields
In this paper, we show exponential lower bounds for the class of homogeneous depth-$5$ circuits over all small finite fields. More formally, we show that there is an explicit family $\{P_d : d \in \mathbb{N}\}$ of polynomials in $\mathsf{VNP}$, where $P_d$ is of degree $d$ in $n = d^{O(1)}$ variables, such that over all finite fields $\mathbb{F}_q$, any homogeneous depth-$5$ circuit which computes $P_d$ must have size at least $\exp(\Omega_q(\sqrt{d}))$. 
To the best of our knowledge, this is the first super-polynomial lower bound for this class for any field $\mathbb{F}_q \neq \mathbb{F}_2$. 
Our proof builds up on the ideas developed on the way to proving lower bounds for homogeneous depth-$4$ circuits [GKKS13, FLMS13, KLSS14, KS14] and for non-homogeneous depth-$3$ circuits over finite fields [GK98, GR00]. Our key insight is to look at the space of shifted partial derivatives of a polynomial as a space of functions from $\mathbb{F}_q^n \rightarrow \mathbb{F}_q$ as opposed to looking at them as a space of formal polynomials and builds over a tighter analysis of the lower bound of Kumar and Saraf [KS14].