We show that the GCD of two univariate polynomials can be computed by (piece-wise) algebraic circuits of constant depth and polynomial size over any sufficiently large field, regardless of the characteristic. This extends a recent result of Andrews & Wigderson who showed such an upper bound over fields of zero or large characteristic. Our proofs are based on a recent work of Bhattacharjee, Kumar, Rai, Ramanathan, Saptharishi \& Saraf that shows closure of constant depth algebraic circuits under factorization. On our way to the proof, we show that any $n$-variate symmetric polynomial $P$ that has a small constant depth algebraic circuit can be written as the composition of a small constant depth algebraic circuit with elementary symmetric polynomials. This statement is a constant depth version of a result of Bläser & Jindal, who showed this for algebraic circuits of unbounded depth. As an application of our techniques, we also strengthen the closure results for factors of constant-depth circuits in the work of Bhattacharjee et al. over fields for small characteristic.

We show that algebraic formulas and constant-depth circuits are closed under taking factors. In other words, we show that if a multivariate polynomial over a field of characteristic zero has a small constant-depth circuit or formula, then all its factors can be computed by small constant-depth circuits or formulas respectively.

We show that Reed-Solomon codes of dimension k and block length n over any finite field F can be deterministically list decoded from agreement √(k−1)n in time poly(n, log|F|).

While efficient randomized algorithms for factorization of polynomials given by algebraic circuits have been known for decades, obtaining an even slightly non-trivial deterministic algorithm for this problem has remained an open question of great interest. This is true even when the input algebraic circuit has additional structure, for instance, when it is a constant-depth circuit. Indeed, no efficient deterministic algorithms are known even for the seemingly easier problem of factoring sparse polynomials or even the problem of testing the irreducibility of sparse polynomials.In this work, we make progress on these questions: we design a deterministic algorithm that runs in subexponential time, and when given as input a constant-depth algebraic circuit C over the field of rational numbers, it outputs algebraic circuits (of potentially unbounded depth) for all the irreducible factors of C, together with their multiplicities. In particular, we give the first subexponential time deterministic algorithm for factoring sparse polynomials.For our proofs, we rely on a finer understanding of the structure of power series roots of constant-depth circuits and the analysis of the Kabanets-Impagliazzo generator. In particular, we show that the Kabanets-Impagliazzo generator constructed using low-degree hard polynomials (explicitly constructed in the work of Limaye, Srinivasan & Tavenas) preserves not only the non-zeroness of small constant-depth circuits (as shown by Chou, Kumar & Solomon), but also their irreducibility and the irreducibility of their factors.

We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon (FRS) codes can be made to run in$\tilde{O}(n)$time. Univariate multiplicity codes and FRS codes are natural variants of Reed-Solomon codes that were discovered and studied for their applications to list decoding. It is known that for every$\varepsilon > 0$, and rate$r\in(0,1)$, there exist explicit families of these codes that have rate$r$and can be list decoded from a$(1-r-\varepsilon)$fraction of errors with constant list size in polynomial time (Guruswami & Wang (IEEE Trans. Inform. Theory 2013) and Kopparty, Ron-Zewi, Saraf & Wootters (SIAM J. Comput. 2023)). In this work, we present randomized algorithms that perform the above list-decoding tasks in$\tilde{O}(n)$, where$n$is the block-length of the code. Our algorithms have two main components. The first component builds upon the lattice-based approach of Alekhnovich (IEEE Trans. Inf. Theory 2005), who designed a$\tilde{O}(n)$time list-decoding algorithm for Reed-Solomon codes approaching the Johnson radius. As part of the second component, we design$\tilde{O}(n)$time algorithms for two natural algebraic problems: given a$(m+2)$-variate polynomial$Q(x, y_{0}, \ldots, y_{m})=\tilde{Q}(x)+\sum\nolimits_{i=0}^{m} Q_{i}(x) \cdot y_{i}$the first algorithm solves order-m linear differential equations of the form$Q\left(x, f(x), \frac{d f}{d x}, \ldots, \frac{d^{m} f}{d x^{m}}\right) \equiv 0$while the second solves functional equations of the form$Q(x, f(x), f(\gamma x), \ldots, f(\gamma^{m}x))\equiv 0$, where$m$is an arbitrary constant and$\gamma$is a field element of sufficiently high order. These algorithms can be viewed as generalizations of classical$\tilde{O}(n)$time algorithms of Sieveking (Computing 1972) and Kung (Numer. Math. 1974) for computing the modular inverse of a power series, and might be of independent interest.

We prove that the most natural low-degree test for polynomials over finite fields is “robust” in the high-error regime for linear-sized fields. Specifically we consider the “local” agreement of a function$f:\mathbb{F}_{q}^{m}\rightarrow \mathbb{F}_{q}$from the space of degree-d polynomials, i.e., the expected agreement of the function from univariate degree-d polynomials over a randomly chosen line in$\mathbb{F}_{q}^{m}$, and prove that if this local agreement is$\varepsilon\geq\Omega((d/q)^{\tau}))$for some fixed$\tau > 0$, then there is a global degree-d polynomial$Q:\mathbb{F}_{q}^{m}\rightarrow \mathbb{F}_{q}$with agreement nearly$\varepsilon$with$f$. This settles a long-standing open question in the area of low-degree testing, yielding an$O(d)$-query robust test in the “high-error” regime (i.e., when$\varepsilon < 1/2)$. The previous results in this space either required$\varepsilon > 1/2$(Polishchuk & Spielman, STOC 1994), or$q=\Omega(d^{4})$(Arora & Sudan, Combinatorica 2003), orneeded to measure local distance on 2-dimensional “planes” rather than one-dimensional lines leading to$\Omega(d^{2})$-query complexity (Raz & Safra, STOC 1997). Our analysis follows the spirit of most previous analyses in first analyzing the low-variable case$(m=O(1))$and then “boot-strapping” to general multivariate settings. Our main technical novelty is a new analysis in the bivariate setting that exploits a previously known connection between multivariate factorization and finding (or testing) low-degree polynomials, in a non “black-box” manner. This connection was used roughly in a black-box manner in the work of Arora & Sudan — and we show that opening up this black box and making some delicate choices in the analysis leads to our essentially optimal analysis. A second contribution is a bootstrapping analysis which manages to lift analyses for$m=2$directly to analyses for general$m$, where previous works needed to work with$m=3$or$m=4$— arguably this bootstrapping is significantly simpler than those in prior works.

For every constant d, we design a subexponential time deterministic algorithm that takes as input a multivariate polynomial f given as a constant depth algebraic circuit over the field of rational numbers, and outputs all irreducible factors of f of degree at most d together with their respective multiplicities. Moreover, if f is a sparse polynomial, then the algorithm runs in quasipolynomial time.

Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate multipoint evaluation over any finite field \(\mathbb {F}\) that outputs the evaluations of an m -variate polynomial of degree less than d in each variable at N points in time, \(\begin{equation*} (d^m+N)^{1+o(1)}\cdot {{\sf poly}}(m,d,\log |\mathbb {F}|), \end{equation*}\) for all \(m\in \mathbb {N}\) and all sufficiently large \(d\in \mathbb {N}\) . A previous work of Kedlaya and Umans (FOCS 2008 and SICOMP 2011) achieved the same time complexity when the number of variables m is at most \(d^{o(1)}\) and had left the problem of removing this condition as an open problem. A recent work of Bhargava, Ghosh, Kumar, and Mohapatra (STOC 2022) answered this question when the underlying field is not too large and has characteristic less than \(d^{o(1)}\) . In this work, we remove this constraint on the number of variables over all finite fields, thereby answering the question of Kedlaya and Umans over all finite fields. Our algorithm relies on a non-trivial combination of ideas from three seemingly different previously known algorithms for multivariate multipoint evaluation, namely the algorithms of Kedlaya and Umans, that of Björklund, Kaski, and Williams (IPEC 2017 and Algorithmica 2019), and that of Bhargava, Ghosh, Kumar, and Mohapatra, together with a result of Bombieri and Vinogradov from analytic number theory about the distribution of primes in an arithmetic progression. We also present a second algorithm for multivariate multipoint evaluation that is completely elementary and, in particular, avoids the use of the Bombieri–Vinogradov theorem. However, it requires a mild assumption that the field size is bounded by an exponential tower in d of bounded height . More specifically, our second algorithm solves the multivariate multipoint evaluation problem over a finite field \(\mathbb {F}\) in time, \(\begin{equation*} (d^m+N)^{1+o(1)}\cdot {{\sf poly}}(m,d,\log |\mathbb {F}|), \end{equation*}\) for all \(m\in \mathbb {N}\) and all sufficiently large \(d\in \mathbb {N}\) , provided that the size of the finite field \(\mathbb {F}\) is at most \((\exp (\exp (\exp (\cdots (\exp (d)))))\) , where the height of this tower of exponentials is fixed.

The multiplicity Schwartz-Zippel lemma bounds the total multiplicity of zeroes of a multivariate polynomial on a product set. This lemma motivates the multiplicity codes of Kopparty, Saraf and Yekhanin [J. ACM, 2014], who showed how to use this lemma to construct high-rate locally-decodable codes. However, the algorithmic results about these codes crucially rely on the fact that the polynomials are evaluated on a vector space and not an arbitrary product set. In this work, we show how to decode multivariate multiplicity codes of large multiplicities in polynomial time over finite product sets (over fields of large characteristic and zero characteristic). Previously such decoding algorithms were not known even for a positive fraction of errors. In contrast, our work goes all the way to the distance of the code and in particular exceeds both the unique-decoding bound and the Johnson radius. For errors exceeding the Johnson radius, even combinatorial list-decodablity of these codes was not known. Our algorithm is an application of the classical polynomial method directly to the multivariate setting. In particular, we do not rely on a reduction from the multivariate to the univariate case as is typical of many of the existing results on decoding codes based on multivariate polynomials. However, a vanilla application of the polynomial method in the multivariate setting does not yield a polynomial upper bound on the list size. We obtain a polynomial bound on the list size by taking an alternative view of multivariate multiplicity codes. In this view, we glue all the partial derivatives of the same order together using a fresh set$\mathbf {z}$of variables. We then apply the polynomial method by viewing this as a problem over the field$\mathbb {F} (\mathbf {z})$of rational functions in$\mathbf {z}$.

In this work, we present an abstract framework for some algebraic error-correcting codes with the aim of capturing codes that are list-decodable to capacity, along with their decoding algorithms. In the polynomial ideal framework, a code is specified by some ideals in a polynomial ring, messages are polynomials and the encoding of a message polynomial is the collection of residues of that polynomial modulo the ideals. We present an alternate way of viewing this class of codes in terms of linear operators, and show that this alternate view makes their algorithmic list-decodability amenable to analysis. Our framework leads to a new class of codes that we call affine Folded Reed-Solomon codes (which are themselves a special case of the broader class we explore). These codes are common generalizations of the well-studied Folded Reed-Solomon codes and Univariate Multiplicity codes as well as the less-studied Additive Folded Reed-Solomon codes, and lead to a large family of codes that were not previously known/studied. More significantly our framework also captures the algorithmic list-decodability of the constituent codes. Specifically, we present a unified view of the decoding algorithm for ideal-theoretic codes and show that the decodability reduces to the analysis of the distance of some related codes. We show that a good bound on this distance leads to a capacity-achieving performance of the underlying code, providing a unifying explanation of known capacity-achieving results. In the specific case of affine Folded Reed-Solomon codes, our framework shows that they are efficiently list-decodable up to capacity (for appropriate setting of the parameters), thereby unifying the previous results for Folded Reed-Solomon, Multiplicity and Additive Folded Reed-Solomon codes.

We design nearly-linear time numerical algorithms for the problem of multivariate multipoint evaluation over the fields of rational, real and complex numbers. We consider both exact and approximate versions of the algorithm. The input to the algorithms are (1) coefficients of an m-variate polynomial f with degree d in each variable, and (2) points $\mathbf{a}_{1}, \ldots, \mathbf{a}_{N}$ each of whose coordinate has absolute value bounded by one. Approximate version: Given additionally an accuracy parameter t, the algorithm computes rational numbers $\beta_{1}, \ldots, \beta_{N}$ such that $\left|f\left(\mathbf{a}_{i}\right)-\beta_{i}\right| \leq 1 / 2^{t}$ for all i, and has a running time of $\left(\left(N m+d^{m}\right) t\right)^{1+o(1)}$ for all m and all sufficiently large d. Exact version (when over rationals): Given additionally a bound s on the bit-complexity of all the rational numbers in the input and output, the algorithm computes the rational numbers $f\left(\mathbf{a}_{1}\right), \ldots, f\left(\mathbf{a}_{N}\right)$, in time $\left(\left(N m+d^{m}\right) s\right)^{1+o(1)}$ for all m and all sufficiently large d. Our results also naturally extend to the case when the input is over the field of real or complex numbers under an appropriate standard model of representation of field elements in such fields.Prior to this work, a nearly-linear time algorithm for multivariate multipoint evaluation (exact or approximate) over any infinite field appears to be known only for the case of univariate polynomials, and was discovered in a recent work of Moroz [Proc. 62nd FOCS, 2021]. In this work, we extend this result from the univariate to the multivariate setting. However, our algorithm is based on ideas that seem to be conceptually different from those of Moroz [Proc. 62nd FOCS, 2021] and crucially relies on a recent algorithm of Bhargava, Ghosh, Guo, Kumar & Umans [Proc. 63rd FOCS, 2022] for multivariate multipoint evaluation over finite fields, and known efficient algorithms for the problems of rational number reconstruction and fast Chinese remaindering in computational number theory.

The multiplicity Schwartz-Zippel lemma asserts that over a field, a low-degree polynomial cannot vanish with high multiplicity very often on a sufficiently large product set. Since its discovery in a work of Dvir, Kopparty, Saraf and Sudan [DKSS13], the lemma has found numerous applications in both math and computer science; in particular, in the definition and properties of multiplicity codes by Kopparty, Saraf and Yekhanin [KSY14]. In this work, we show how to algorithmize the multiplicity Schwartz-Zippel lemma for arbitrary product sets over any field. In other words, we give an efficient algorithm for unique decoding of multivariate multiplicity codes from half their minimum distance on arbitrary product sets over all fields. Previously, such an algorithm was known either when the underlying product set had a nice algebraic structure (for instance, was a subfield) [Kop15] or when the underlying field had large (or zero) characteristic, the multiplicity parameter was sufficiently large and the multiplicity code had distance bounded away from 1 [BHKS21b]. In particular, even unique decoding of bivariate multiplicity codes with multiplicity two from half their minimum distance was not known over arbitrary product sets over any field. Our algorithm builds upon a result of Kim & Kopparty [KK17] who gave an algorithmic version of the Schwartz-Zippel lemma (without multiplicities) or equivalently, an efficient algorithm for unique decoding of Reed-Muller codes over arbitrary product sets. We introduce a refined notion of distance based on the multiplicity Schwartz-Zippel lemma and design a unique decoding algorithm for this distance measure. On the way, we give an alternate analysis of Forney's classical generalized minimum distance decoder that might be of independent interest. * The full version of the paper which includes the missing proofs can be accessed at [BHKS21a]. Research of the first, second and fourth authors supported by the Department of Atomic Energy, Government of India, under project 12-R&D-TFR-5.01-0500. This work was done while the first author was at TIFR, where he was supported in part by the Google PhD Fellowship and at the Simons Institute for the Theory of Computing where he was supported by the Simons-Berkeley Postdoctoral Fellowship. Research of the second author supported in part by the Swarnajayanti Fellowship.

Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of inputs. Besides being a natural and fundamental question in computer algebra on its own, fast algorithms for this problem are also closely related to fast algorithms for other natural algebraic questions such as polynomial factorization and modular composition. And while nearly linear time algorithms have been known for the univariate instance of multipoint evaluation for close to five decades due to a work of Borodin and Moenck [ 7 ], fast algorithms for the multivariate version have been much harder to come by. In a significant improvement to the state-of-the-art for this problem, Umans [ 25 ] and Kedlaya & Umans [ 16 ] gave nearly linear time algorithms for this problem over field of small characteristic and over all finite fields, respectively, provided that the number of variables n is at most \(d^{o(1)}\) where the degree of the input polynomial in every variable is less than d . They also stated the question of designing fast algorithms for the large variable case (i.e., \(n \notin d^{o(1)}\) ) as an open problem. In this work, we show that there is a deterministic algorithm for multivariate multipoint evaluation over a field \(\mathbb {F}_{q}\) of characteristic p , which evaluates an n -variate polynomial of degree less than d in each variable on N inputs in time \(\begin{equation*} \left((N + d^n)^{1 + o(1)}\text{poly}(\log q, d, n, p)\right), \end{equation*}\) provided that p is at most d o (1) , and q is at most (exp (exp (exp (...(exp ( d ))))), where the height of this tower of exponentials is fixed. When the number of variables is large (e.g., n ∉ d o (1) ), this is the first nearly linear time algorithm for this problem over any (large enough) field. Our algorithm is based on elementary algebraic ideas, and this algebraic structure naturally leads to the following two independently interesting applications: — We show that there is an algebraic data structure for univariate polynomial evaluation with nearly linear space complexity and sublinear time complexity over finite fields of small characteristic and quasipolynomially bounded size. This provides a counterexample to a conjecture of Miltersen [ 21 ] who conjectured that over small finite fields, any algebraic data structure for polynomial evaluation using polynomial space must have linear query complexity. — We also show that over finite fields of small characteristic and quasipolynomially bounded size, Vandermonde matrices are not rigid enough to yield size-depth tradeoffs for linear circuits via the current quantitative bounds in Valiant’s program [ 26 ]. More precisely, for every fixed prime p , we show that for every constant ɛ > 0, and large enough n , the rank of any \(n \times n\) Vandermonde matrix V over the field \(\mathbb {F}_{p^a}\) can be reduced to ( n /exp (Ω (poly(ɛ)log 0.53 n ))) by changing at most n Θ (ɛ) entries in every row of V , provided a ≤ poly(log n ). Prior to this work, similar upper bounds on rigidity were known only for special Vandermonde matrices. For instance, the Discrete Fourier Transform matrices and Vandermonde matrices with generators in a geometric progression [ 9 ].

Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate multipoint evaluation over any finite field F that outputs the evaluations of an m-variate polynomial of degree less than d in each variable at N points in time $(d^{m}+N)^{1+o(1)}$ poly $(m,\ d,\ \log|\mathbb{F}|)$ for all $m\in \mathbb{N}$ and all sufficiently large $d\in \mathbb{N}$. A previous work of Kedlaya and Umans (FOCS 2008, SICOMP 2011) achieved the same time complexity when the number of variables m is at most $d^{o(1)}$ and had left the problem of removing this condition as an open problem. A recent work of Bhargava, Ghosh, Kumar and Mohapatra (STOC 2022) answered this question when the underlying field is not too large and has characteristic less than $d^{o(1)}$. In this work, we remove this constraint on the number of variables over all finite fields, thereby answering the question of Kedlaya and Umans over all finite fields. Our algorithm relies on a non-trivial combination of ideas from three seemingly different previously known algorithms for multivariate multipoint evaluation, namely the algorithms of Kedlaya and Umans, that of Björklund, Kaski and Williams (IPEC 2017, Algorithmica 2019), and that of Bhargava, Ghosh, Kumar and Mohapatra, together with a result of Bombieri and Vinogradov from analytic number theory about the distribution of primes in an arithmetic progression. We also present a second algorithm for multivariate multipoint evaluation that is completely elementary and in particular, avoids the use of the Bombieri-Vinogradov Theorem. However, it requires a mild assumption that the field size is bounded by an exponential-tower in d of bounded height.

Assuming that the Permanent polynomial requires algebraic circuits of exponential size, we show that the class VNP does not have efficiently computable equations. In other words, any nonzero polynomial that vanishes on the coefficient vectors of all polynomials in the class VNP requires algebraic circuits of super-polynomial size. In a recent work of Chatterjee and the authors (FOCS 2020), it was shown that the subclasses of VP and VNP consisting of polynomials with bounded integer coefficients do have equations with small algebraic circuits. Their work left open the possibility that these results could perhaps be extended to all of VP or VNP. The results in this paper show that assuming the hardness of Permanent, at least for VNP, allowing polynomials with large coefficients does indeed incur a significant blow up in the circuit complexity of equations.

Multipoint evaluation is the computational task of evaluating a polynomial given as a list of coefficients at a given set of inputs. Besides being a natural and fundamental question in computer algebra on its own, fast algorithms for this problem are also closely related to fast algorithms for other natural algebraic questions like polynomial factorization and modular composition. And while nearly linear time algorithms have been known for the univariate instance of multipoint evaluation for close to five decades due to a work of Borodin and Moenck, fast algorithms for the multivariate version have been much harder to come by. In a significant improvement to the state of art for this problem, Umans and Kedlaya & Umans gave nearly linear time algorithms for this problem over field of small characteristic and over all finite fields respectively, provided that the number of variables n is at most do(1) where the degree of the input polynomial in every variable is less than d. They also stated the question of designing fast algorithms for the large variable case (i.e. n ∉ do(1)) as an open problem.

Abstract Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity Rossman (SIAM J. Comput. 43:256–279, 2014), DNF sparsification Gopalan et al. (Comput. Complex. 22:275–310 2013), randomness extractors Li et al. (In: APPROX-RANDOM, LIPIcs 116:51:1–13, 2018), and recent advances on the Erdős-Rado sunflower conjecture Alweiss et al. (In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC. Association for Computing Machinery, New York, NY, USA, 2020) Lovett et al. (From dnf compression to sunflower theorems via regularity, 2019) Rao (Discrete Anal. 8,2020). The recent breakthrough of Alweiss, Lovett, Wu and Zhang Alweiss et al. (In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC. Association for Computing Machinery, New York, NY, USA, 2020) gives an improved bound on the maximum size of a w-set system that excludes a robust sunflower. In this paper, we use this result to obtain an $$\exp (n^{1/2-o(1)})$$ exp ( n 1 / 2 - o ( 1 ) ) lower bound on the monotone circuit size of an explicit n-variate monotone function, improving the previous best known $$\exp (n^{1/3-o(1)})$$ exp ( n 1 / 3 - o ( 1 ) ) due to Andreev (Algebra and Logic, 26:1–18, 1987) and Harnik and Raz (In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, ACM, New York, 2000). We also show an $$\exp (\varOmega (n))$$ exp ( Ω ( n ) ) lower bound on the monotone arithmetic circuit size of a related polynomial via a very simple proof. Finally, we introduce a notion of robust clique-sunflowers and use this to prove an $$n^{\varOmega (k)}$$ n Ω ( k ) lower bound on the monotone circuit size of the CLIQUE function for all $$k \leqslant n^{1/3-o(1)}$$ k ⩽ n 1 / 3 - o ( 1 ) , strengthening the bound of Alon and Boppana (Combinatorica, 7:1–22, 1987).

A hitting-set generator (HSG) is a polynomial map ${{\mathsf{Gen}}}:{\mathbb{F}}^k \to {\mathbb{F}}^n$ such that for all $n$-variate polynomials $C$ of small enough circuit size and degree, if $C$ is nonzero, then $C\circ {{\mathsf{Gen}}}$ is nonzero. In this paper, we give a new construction of such an HSG assuming that we have an explicit polynomial of sufficient hardness. Formally, we prove the following result over any field ${\mathbb{F}}$ of characteristic zero: Let $k\in {\mathbb{N}}$ and $\delta > 0$ be arbitrary constants. Suppose ${\left\{ {P_d} \right\}}_{d\in {\mathbb{N}}}$ is an explicit family of $k$-variate polynomials such that $\deg P_d = d$ and $P_d$ requires algebraic circuits of size $d^\delta$. Then, there are explicit hitting sets of polynomial size for the class ${\mathsf{VP}}$. This is the first HSG in the algebraic setting that yields a complete derandomization of polynomial identity testing (PIT) for general circuits from a suitable algebraic hardness assumption. Unlike the prior constructions of such maps [N. Nisan and A. Wigderson, J. Comput. System Sci., 49 (1994), pp. 149--167; V. Kabanets and R. Impagliazzo, Comput. Complexity, 13 (2004), pp. 1--46; M. Agrawal, S. Ghosh, and N.Saxena, Proc. Natl. Acad. Sci. USA, 116 (2019), pp. 8107--8118; M. Kumar, R. Saptharishi, and A. Tengse, Proceedings of the \textup30th Annual ACM-SIAM Symposium on Discrete Algorithms, 2019, pp. 639--646], our construction is purely algebraic and does not rely on the notion of combinatorial designs. As a direct consequence, we show that even saving a single point from the “trivial” explicit, exponential sized hitting sets for constant-variate polynomials of low individual degree which are computable by small circuits implies a deterministic polynomial time algorithm for PIT. More precisely, we show the following: Let $k\in {\mathbb{N}}$ and $\delta > 0$ be arbitrary constants. Suppose for every $s$ large enough, there is an explicit hitting set of size at most $((s+1)^k - 1)$ for the class of $k$-variate polynomials of individual degree $s$ that are computable by size $s^\delta$ circuits. Then there is an explicit hitting set of size ${\operatorname{poly}}(s)$ for the class of $s$-variate polynomials, of degree $s$, that are computable by size $s$ circuits. As a consequence, we give a deterministic polynomial time construction of hitting sets for algebraic circuits, if a strengthening of the $\tau$-conjecture of Shub and Smale [M. Shub and S. Smale, Duke Math. J., 81 (1995), pp. 47--54; S. Smale, Math. Intelligencer, 20 (1998), pp. 7--15] is true.

In this work, we present an abstract framework for some algebraic error-correcting codes with the aim of capturing codes that are list-decodable to capacity, along with their decoding algorithm. In the polynomial ideal framework, a code is specified by some ideals in a polynomial ring, messages are polynomials and their encoding is the residue modulo the ideals. We present an alternate way of viewing this class of codes in terms of linear operators, and show that this alternate view makes their algorithmic list-decodability amenable to analysis. Our framework leads to a new class of codes that we call affine Folded Reed-Solomon codes (which are themselves a special case of the broader class we explore). These codes are common generalizations of the well-studied Folded Reed-Solomon codes and Multiplicity codes, while also capturing the less-studied Additive Folded Reed-Solomon codes as well as a large family of codes that were not previously known/studied. More significantly our framework also captures the algorithmic list-decodability of the constituent codes. Specifically, we present a unified view of the decoding algorithm for ideal theoretic codes and show that the decodability reduces to the analysis of the distance of some related codes. We show that good bounds on this distance lead to capacity-achieving performance of the underlying code, providing a unifying explanation of known capacity-achieving results. In the specific case of affine Folded Reed-Solomon codes, our framework shows that they are list-decodable up to capacity (for appropriate setting of the parameters), thereby unifying the previous results for Folded Reed-Solomon, Multiplicity and Additive Folded Reed-Solomon codes.

The determinantal complexity of a polynomial P ∈ 𝔽[x₁, …, x_n] over a field 𝔽 is the dimension of the smallest matrix M whose entries are affine functions in 𝔽[x₁, …, x_n] such that P = Det(M). We prove that the determinantal complexity of the polynomial ∑_{i = 1}^n x_i^n is at least 1.5n - 3. For every n-variate polynomial of degree d, the determinantal complexity is trivially at least d, and it is a long standing open problem to prove a lower bound which is super linear in max{n,d}. Our result is the first lower bound for any explicit polynomial which is bigger by a constant factor than max{n,d}, and improves upon the prior best bound of n + 1, proved by Alper, Bogart and Velasco [Jarod Alper et al., 2017] for the same polynomial.

We show that there is an equation of degree at most poly(n) for the (Zariski closure of the) set of the non-rigid matrices: that is, we show that for every large enough field 𝔽, there is a non-zero n²-variate polynomial P ∈ 𝔽[x_{1, 1}, …, x_{n, n}] of degree at most poly(n) such that every matrix M which can be written as a sum of a matrix of rank at most n/100 and a matrix of sparsity at most n²/100 satisfies P(M) = 0. This confirms a conjecture of Gesmundo, Hauenstein, Ikenmeyer and Landsberg [Fulvio Gesmundo et al., 2016] and improves the best upper bound known for this problem down from exp(n²) [Abhinav Kumar et al., 2014; Fulvio Gesmundo et al., 2016] to poly(n). We also show a similar polynomial degree bound for the (Zariski closure of the) set of all matrices M such that the linear transformation represented by M can be computed by an algebraic circuit with at most n²/200 edges (without any restriction on the depth). As far as we are aware, no such bound was known prior to this work when the depth of the circuits is unbounded. Our methods are elementary and short and rely on a polynomial map of Shpilka and Volkovich [Amir Shpilka and Ilya Volkovich, 2015] to construct low degree "universal" maps for non-rigid matrices and small linear circuits. Combining this construction with a simple dimension counting argument to show that any such polynomial map has a low degree annihilating polynomial completes the proof. As a corollary, we show that any derandomization of the polynomial identity testing problem will imply new circuit lower bounds. A similar (but incomparable) theorem was proved by Kabanets and Impagliazzo [Valentine Kabanets and Russell Impagliazzo, 2004].

The multiplicity Schwartz-Zippel lemma bounds the total multiplicity of zeroes of a multivariate polynomial on a product set. This lemma motivates the multiplicity codes of Kopparty, Saraf and Yekhanin [J. ACM, 2014], who showed how to use this lemma to construct high-rate locally-decodable codes. However, the algorithmic results about these codes crucially rely on the fact that the polynomials are evaluated on a vector space and not an arbitrary product set.

In this work, we prove new relations between the bias of multilinear forms, the correlation between multilinear forms and lower degree polynomials, and the rank of tensors over F₂. We show the following results for multilinear forms and tensors. Correlation bounds. We show that a random d-linear form has exponentially low correlation with low-degree polynomials. More precisely, for d = 2^{o(k)}, we show that a random d-linear form f(X₁,X₂, … , X_d) : (F₂^{k}) ^d → F₂ has correlation 2^{-k(1-o(1))} with any polynomial of degree at most d/2 with high probability. This result is proved by giving near-optimal bounds on the bias of a random d-linear form, which is in turn proved by giving near-optimal bounds on the probability that a sum of t random d-dimensional rank-1 tensors is identically zero. Tensor rank vs Bias. We show that if a 3-dimensional tensor has small rank then its bias, when viewed as a 3-linear form, is large. More precisely, given any 3-dimensional tensor T: [k]³ → F₂ of rank at most t, the bias of the 3-linear form f_T(X₁, X₂, X₃) : = ∑_{(i₁, i₂, i₃) ∈ [k]³} T(i₁, i₂, i₃)⋅ X_{1,i₁}⋅ X_{2,i₂}⋅ X_{3,i₃} is at least (3/4)^t. This bias vs tensor-rank connection suggests a natural approach to proving nontrivial tensor-rank lower bounds. In particular, we use this approach to give a new proof that the finite field multiplication tensor has tensor rank at least 3.52 k, which is the best known rank lower bound for any explicit tensor in three dimensions over F₂. Moreover, this relation between bias and tensor rank holds for d-dimensional tensors for any fixed d.

We study the problem of constructing explicit families of matrices which cannot be expressed as a product of a few sparse matrices. In addition to being a natural mathematical question on its own, this problem appears in various incarnations in computer science; the most significant being in the context of lower bounds for algebraic circuits which compute linear transformations, matrix rigidity and data structure lower bounds. We first show, for every constant $d$, a deterministic construction in subexponential time of a family $\{M_n\}$ of $n \times n$ matrices which cannot be expressed as a product $M_n = A_1 \cdots A_d$ where the total sparsity of $A_1,\ldots,A_d$ is less than $n^{1+1/(2d)}$. In other words, any depth-$d$ linear circuit computing the linear transformation $M_n\cdot x$ has size at least $n^{1+Ω(1/d)}$. This improves upon the prior best lower bounds for this problem, which are barely super-linear, and were obtained by a long line of research based on the study of super-concentrators (albeit at the cost of a blow up in the time required to construct these matrices). We then outline an approach for proving improved lower bounds through a certain derandomization problem, and use this approach to prove asymptotically optimal quadratic lower bounds for natural special cases, which generalize many of the common matrix decompositions.

We show that any Algebraic Branching Program (ABP) computing the polynomial ∑_{i=1}^n xⁿ_i has at least Ω(n²) vertices. This improves upon the lower bound of Ω(nlog n), which follows from the classical result of Baur and Strassen [Volker Strassen, 1973; Walter Baur and Volker Strassen, 1983], and extends the results of Kumar [Mrinal Kumar, 2019], which showed a quadratic lower bound for homogeneous ABPs computing the same polynomial. Our proof relies on a notion of depth reduction which is reminiscent of similar statements in the context of matrix rigidity, and shows that any small enough ABP computing the polynomial ∑_{i=1}^n xⁿ_i can be depth reduced to essentially a homogeneous ABP of the same size which computes the polynomial ∑_{i=1}^n xⁿ_i + ε(𝐱), for a structured "error polynomial" ε(𝐱). To complete the proof, we then observe that the lower bound in [Mrinal Kumar, 2019] is robust enough and continues to hold for all polynomials ∑_{i=1}^n xⁿ_i + ε(𝐱), where ε(𝐱) has the appropriate structure.

Schur Polynomials are families of symmetric polynomials that have been classically studied in Combinatorics and Algebra alike. They play a central role in the study of Symmetric functions, in Representation theory [Stanley, 1999], in Schubert calculus [Ledoux and Malham, 2010] as well as in Enumerative combinatorics [Gasharov, 1996; Stanley, 1984; Stanley, 1999]. In recent years, they have also shown up in various incarnations in Computer Science, e.g, Quantum computation [Hallgren et al., 2000; Ryan O'Donnell and John Wright, 2015] and Geometric complexity theory [Ikenmeyer and Panova, 2017]. However, unlike some other families of symmetric polynomials like the Elementary Symmetric polynomials, the Power Symmetric polynomials and the Complete Homogeneous Symmetric polynomials, the computational complexity of syntactically computing Schur polynomials has not been studied much. In particular, it is not known whether Schur polynomials can be computed efficiently by algebraic formulas. In this work, we address this question, and show that unless every polynomial with a small algebraic branching program (ABP) has a small algebraic formula, there are Schur polynomials that cannot be computed by algebraic formula of polynomial size. In other words, unless the algebraic complexity class VBP is equal to the complexity class VF, there exist Schur polynomials which do not have polynomial size algebraic formulas. As a consequence of our proof, we also show that computing the determinant of certain generalized Vandermonde matrices is essentially as hard as computing the general symbolic determinant. To the best of our knowledge, these are one of the first hardness results of this kind for families of polynomials which are not multilinear. A key ingredient of our proof is the study of composition of well behaved algebraically independent polynomials with a homogeneous polynomial, and might be of independent interest.

For every constant , we show that there is a family {PN, c} of polynomials whose degree and algebraic circuit complexity are polynomially bounded in the number of variables, that satisfies the following properties: For every family {fn} of polynomials in VP, where fn is an n variate polynomial of degree at most ncwith bounded integer coefficients and for N=nc+nn, PN, c vanishes on the coefficient vector of fn. There exists a family {hn} of polynomials where hn is an n variate polynomial of degree at most ncwith bounded integer coefficients such that for N=nc+nn, PN, c does not vanish on the coefficient vector of hn. In other words, there are efficiently computable equations for polynomials in VP that have small integer coefficients. In fact, we also prove an analogous statement for the seemingly larger class VNP. Thus, in this setting of polynomials with small integer coefficients, this provides evidence against a natural proof like barrier for proving algebraic circuit lower bounds, a framework for which was proposed in the works of Forbes, Shpilka and Volk [1], and Grochow, Kumar, Saks and Saraf [2]. Our proofs are elementary and rely on the existence of (non-explicit) hitting sets for VP (and VNP) to show that there are efficiently constructible, low degree equations for these classes and also extend to finite fields of small size. Our proofs are elementary and rely on the existence of (non-explicit) hitting sets for VP (and VNP) to show that there are efficiently constructible, low degree equations for these classes and also extend to finite fields of small size.

A hitting-set generator (HSG) is a polynomial map Gen:Fk→ Fnsuch that for all n-variate polynomials Q of small enough circuit size and degree, if Q is non-zero, then Q o Gen is non-zero. In this paper, we give a new construction of such a HSG assuming that we have an explicit polynomial of sufficient hardness in the sense of approximative or border complexity. Formally, we prove the following result over any characteristic zero field F: Suppose P(z1,..., zk) is an explicit k-variate degree d polynomial that is not in the border of circuits of size s. Then, there is an explicit hitting-set generator Gen(P): F2k→ Fnsuch that every non-zero n-variate degree D polynomial Q(x) in the border of size s' circuits satisfies Q ≠ 0 ⇒ Q o Gen(P) ≠ 0 provided n10kd Ds'0 be a constant and k be a large enough constant. Suppose, for every s ≥ k, there is an explicit hitting set of size sk-δfor all degree s polynomials in the border of k-variate size s algebraic circuits. Then, there is an explicit hitting set of size poly(s) for the border s-variate algebraic circuits of size s and degree s. Unlike the prior constructions of such maps (e.g.[NW94], [KI04], [AGS19], [KST19]), our construction is purely algebraic and does not rely on the notion of combinatorial designs.

We show that any $n$-variate polynomial computable by a syntactically multilinear circuit of size $\operatorname{poly}(n)$ can be computed by a depth-$4$ syntactically multilinear ($ΣΠΣΠ$) circuit of size at most $\exp\left({O\left(\sqrt{n\log n}\right)}\right)$. For degree $d = ω(n/\log n)$, this improves upon the upper bound of $\exp\left({O(\sqrt{d}\log n)}\right)$ obtained by Tavenas~\cite{T15} for general circuits, and is known to be asymptotically optimal in the exponent when $d < n^ε$ for a small enough constant $ε$. Our upper bound matches the lower bound of $\exp\left({Ω\left(\sqrt{n\log n}\right)}\right)$ proved by Raz and Yehudayoff~\cite{RY09}, and thus cannot be improved further in the exponent. Our results hold over all fields and also generalize to circuits of small individual degree. More generally, we show that an $n$-variate polynomial computable by a syntactically multilinear circuit of size $\operatorname{poly}(n)$ can be computed by a syntactically multilinear circuit of product-depth $Δ$ of size at most $\exp\left(O\left(Δ\cdot (n/\log n)^{1/Δ} \cdot \log n\right)\right)$. It follows from the lower bounds of Raz and Yehudayoff (CC 2009) that in general, for constant $Δ$, the exponent in this upper bound is tight and cannot be improved to $o\left(\left(n/\log n\right)^{1/Δ}\cdot \log n\right)$.

The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that any nonzero polynomial f(xi, …, xn) of degree at most s will evaluate to a nonzero value at some point on a grid with |S| > s. Thus, there is a deterministic polynomial identity test (PIT) for all degrees size-s algebraic circuits in n variables that runs in time poly(s) · (s + 1)n. In a surprising recent result, Agrawal, Ghosh and Saxena (STOC 2018) showed any deterministic blackbox PIT algorithm for degree-s, size-s, n-variate circuits with running time as bad as (sn0.5−δ) Huge(n), where δ > 0 and Huge(n) is an arbitrary function, can be used to construct blackbox PIT algorithms for degree-s size s circuits with running time sexp(exp(O(log* s))). Agrawal et al. asked if a similar conclusion followed if their hypothesis was weakened to having deterministic PIT with running time so(n) · Huge(n). In this paper, we answer their question in the affirmative. We show that, given a deterministic blackbox PIT that runs in time so(n) · Huge(n) for all degree-s size-s algebraic circuits over n variables, we can obtain a deterministic blackbox PIT that runs in time sexp(exp(O(log* s))) for all degree-s size-s algebraic circuits over n variables. In other words, any blackbox PIT with just a slightly nontrivial exponent of s compared to the trivial sO(n) test can be used to give a nearly polynomial time blackbox PIT algorithm.

Surprising and beautiful depth reduction results show that sufficiently strong lower bounds for bounded-depth arithmetic circuits imply superpolynomial lower bounds for general arithmetic circuits. Motivated by this, in the last few years, there has been renewed interest in the question of proving superpolynomial lower bounds for bounded-depth circuits, starting with homogeneous depth-4 circuits. Following a sequence of recent results, we now know an $n^{\Omega(\sqrt{d})}$ lower bound for homogeneous depth-4 circuits, for an explicit polynomial of degree $d$ in $n$ variables. It is also known that any asymptotic improvement in the exponent of this lower bound implies a superpolynomial lower bound for general arithmetic circuits. An intriguing fact is that in spite of all this recent progress which seems to bring us to the edge of the chasm at depth-4, it appears to shine very little light on the question of lower bounds for even slight generalizations of homogeneous depth-4 circuits. Indeed, superquadratic lower bounds are not known for even nonhomogeneous depth-4 circuits, or homogeneous depth-5 circuits, and supercubic lower bounds are not known for nonhomogeneous depth-3 circuits. In this paper, we study homogeneous depth-5 circuits, with the aim of proving superpolynomial lower bounds for them and understanding their computational power and limitations when compared to homogeneous depth-4 circuits. We prove the following results. Depth-$5$ versus depth-$4$ circuits. We show that there is a family of polynomials $\{P_n\}$, where $P_n$ is a polynomial in $n$ variables of degree at most $d=O(\log^2n)$, such that $P_n$ can be computed by linear sized homogeneous depth-5 circuits; $P_n$ can be computed by $\operatorname{poly}(n)$ sized nonhomogeneous depth-3 circuits; and any homogeneous depth-4 circuit computing $P_n$ must have size at least $n^{\Omega(\sqrt{d})}$. This shows that the parameters for the depth reduction results of M. Agrawal and V. Vinay, P. Koiran, and S. Tavenas are tight for extremely restricted classes of arithmetic circuits, for instance homogeneous depth-5 circuits and nonhomogeneous depth-3 circuits, and over an appropriate range of parameters. This also qualitatively improves a result of Kumar and Saraf, which showed that the parameters of depth reductions are optimal for algebraic branching programs. Depth-$5$ circuits over small fields. We show that there is an explicit family $\{P_d\}$ of polynomials, 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 superpolynomial lower bound for this class for any field $\mathbb{F}_q\neq\mathbb{F}_2$. Our proof builds on the ideas developed on the way to proving lower bounds for homogeneous depth-4 circuits and for nonhomogeneous depth-3 circuits over finite fields. 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.

In this paper, we study the question of hardness-randomness tradeoffs for bounded depth arithmetic circuits. We show that if there is a family of explicit polynomials {f_n}, where f_n is of degree O(log^2n/log^2 log n) in n variables such that f_n cannot be computed by a depth Delta arithmetic circuits of size poly(n), then there is a deterministic sub-exponential time algorithm for polynomial identity testing of arithmetic circuits of depth Delta-5. This is incomparable to a beautiful result of Dvir et al.[SICOMP, 2009], where they showed that super-polynomial lower bounds for depth Delta circuits for any explicit family of polynomials (of potentially high degree) implies sub-exponential time deterministic PIT for depth Delta-5 circuits of bounded individual degree. Thus, we remove the "bounded individual degree" condition in the work of Dvir et al. at the cost of strengthening the hardness assumption to hold for polynomials of low degree. The key technical ingredient of our proof is the following property of roots of polynomials computable by a bounded depth arithmetic circuit : if f(x_1, x_2, ..., x_n) and P(x_1, x_2, ..., x_n, y) are polynomials of degree d and r respectively, such that P can be computed by a circuit of size s and depth Delta and P(x_1, x_2, ..., x_n, f) equiv 0, then, f can be computed by a circuit of size poly(n, s, r, d^{O(sqrt{d})}) and depth Delta + 3. In comparison, Dvir et al. showed that f can be computed by a circuit of depth Delta + 3 and size poly(n, s, r, d^{t}), where t is the degree of P in y. Thus, the size upper bound in the work of Dvir et al. is non-trivial when t is small but d could be large, whereas our size upper bound is non-trivial when d is small, but t could be large.

An algebraic branching program (ABP) is a directed acyclic graph, with a start vertex s, and end vertex t and each edge having a weight which is an affine form in variables x_1, x_2, ..., x_n over an underlying field. An ABP computes a polynomial in a natural way, as the sum of weights of all paths from s to t, where the weight of a path is the product of the weights of the edges in the path. An ABP is said to be homogeneous if the polynomial computed at every vertex is homogeneous. In this paper, we show that any homogeneous algebraic branching program which computes the polynomial x_1^n + x_2^n + ... + x_n^n has at least Omega(n^2) vertices (and edges). To the best of our knowledge, this seems to be the first non-trivial super-linear lower bound on the number of vertices for a general homogeneous ABP and slightly improves the known lower bound of Omega(n log n) on the number of edges in a general (possibly non-homogeneous) ABP, which follows from the classical results of Strassen (1973) and Baur--Strassen (1983). On the way, we also get an alternate and unified proof of an Omega(n log n) lower bound on the size of a homogeneous arithmetic circuit (follows from [Strassen, 1973] and [Baur-Strassen, 1983]), and an n/2 lower bound (n over reals) on the determinantal complexity of an explicit polynomial [Mignon-Ressayre, 2004], [Cai, Chen, Li, 2010], [Yabe, 2015]. These are currently the best lower bounds known for these problems for any explicit polynomial, and were originally proved nearly two decades apart using seemingly different proof techniques.

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} of polynomials in VNP, where P_d is of degree d in n = d^{O(1)} variables, such that over all finite fields GF(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 non-binary field. Our proof builds up on the ideas developed on the way to proving lower bounds for homogeneous depth-4 circuits [Gupta et al., Fournier et al., Kayal et al., Kumar-Saraf] and for non-homogeneous depth-3 circuits over finite fields [Grigoriev-Karpinski, Grigoriev-Razborov]. Our key insight is to look at the space of shifted partial derivatives of a polynomial as a space of functions from GF(q)^n to GF(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 [Kumar-Saraf].

We prove exponential lower bounds on the size of homogeneous depth 4 arithmetic circuits computing an explicit polynomial in $VP$. Our results hold for the iterated matrix multiplication polynomial---in particular we show that any homogeneous depth 4 circuit computing the (1,1) entry in the product of $n$ generic matrices of dimension $n^{O(1)}$ must have size $n^{\Omega(\sqrt{n})}$. Our results strengthen previous works in two significant ways: (1) Our lower bounds hold for a polynomial in $VP$. Prior to our work, Kayal et al. [Proceedings of FOCS, 2014, pp. 61--70] proved an exponential lower bound for homogeneous depth 4 circuits (over fields of characteristic zero) computing a poly in $VNP$. The best known lower bounds for a depth 4 homogeneous circuit computing a poly in $VP$ was the bound of $n^{\Omega(\log n)}$ by Kayal et al. Our exponential lower bounds also give the first exponential separation between general arithmetic circuits and homogeneous depth 4 arithmetic circuits. In particular they imply that the depth reduction results of Koiran [Theoret. Comput. Sci., 448 (2012), pp. 56--65] and Tavenas [Proceedings of MFCS, 2013] are tight even for reductions to general homogeneous depth 4 circuits (without the restriction of bounded bottom fan-in). (2) Our lower bound holds over all fields. The lower bound of Kayal et al. worked only over fields of characteristic zero. Prior to our work, the best lower bound for homogeneous depth 4 circuits over fields of positive characteristic was $n^{\Omega(\log n)}$ [Kayal et al., Proceedings of FOCS, 2014, pp. 61--70].

In recent years there has been a flurry of activity proving lower bounds for homogeneous depth-4 arithmetic circuits, which has brought us very close to statements that are known to imply VP != VNP. It is a big question to go beyond homogeneity, and in this paper we make progress towards this by considering depth-4 circuits of low algebraic rank, which are a natural extension of homogeneous depth-4 arithmetic circuits. A depth-4 circuit is a representation of an N-variate, degree n polynomial P as P = sum_{i=1}^T Q_{i1} * Q_{i2} * ... * Q_{it} where the Q_{ij} are given by their monomial expansion. Homogeneity adds the constraint that for every i in [T], sum_{j} degree(Q_{ij}) = n. We study an extension where, for every i in [T], the algebraic rank of the set of polynomials {Q_{i1}, Q_{i2}, ... ,Q_{it}} is at most some parameter k. We call this the class of spnew circuits. Already for k=n, these circuits are a strong generalization of the class of homogeneous depth-4 circuits, where in particular t<=n (and hence k<=n). We study lower bounds and polynomial identity tests for such circuits and prove the following results. 1. Lower bounds: We give an explicit family of polynomials {P_n} of degree n in N = n^{O(1)} variables in VNP, such that any spnewn circuit computing P_n has size at least exp{(Omega(sqrt(n)*log(N)))}. This strengthens and unifies two lines of work: it generalizes the recent exponential lower bounds for homogeneous depth-4 circuits [KLSS14, KS-full] as well as the Jacobian based lower bounds of Agrawal et al. which worked for spnew circuits in the restricted setting where T * k <= n. 2. Hitting sets: Let spnewbounded be the class of spnew circuits with bottom fan-in at most d. We show that if d and k are at most poly(log(N)), then there is an explicit hitting set for spnewbounded circuits of size quasipolynomial in N and the size of the circuit. This strengthens a result of Forbes which showed such quasipolynomial sized hitting sets in the setting where d and t are at most poly(log(N)). A key technical ingredient of the proofs is a result which states that over any field of characteristic zero (or sufficiently large characteristic), upto a translation, every polynomial in a set of algebraically dependent polynomials can be written as a function of the polynomials in the transcendence basis. We believe this may be of independent interest. We combine this with shifted partial derivative based methods to obtain our final results.

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<=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 >= n^{Omega(sqrt(n))}. This strengthens a recent result of Kayal and Saha [Kayal/Saha, ECCC 2014] 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 [Kayal/Saha, ECCC 2014]. 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<=N^{mu} for any constant mu<1/2. We get quasipolynomial running time when s

We say that a circuit $C$ over a field $F$ functionally computes an $n$-variate polynomial $P$ if for every $x \in \{0,1\}^n$ we have that $C(x) = P(x)$. This is in contrast to syntactically computing $P$, when $C \equiv P$ as formal polynomials. In this paper, we study the question of proving lower bounds for homogeneous depth-$3$ and depth-$4$ arithmetic circuits for functional computation. We prove the following results : 1. Exponential lower bounds homogeneous depth-$3$ arithmetic circuits for a polynomial in $VNP$. 2. Exponential lower bounds for homogeneous depth-$4$ arithmetic circuits with bounded individual degree for a polynomial in $VNP$. Our main motivation for this line of research comes from our observation that strong enough functional lower bounds for even very special depth-$4$ arithmetic circuits for the Permanent imply a separation between ${\#}P$ and $ACC$. Thus, improving the second result to get rid of the bounded individual degree condition could lead to substantial progress in boolean circuit complexity. Besides, it is known from a recent result of Kumar and Saptharishi [KS15] that over constant sized finite fields, strong enough average case functional lower bounds for homogeneous depth-$4$ circuits imply superpolynomial lower bounds for homogeneous depth-$5$ circuits. Our proofs are based on a family of new complexity measures called shifted evaluation dimension, and might be of independent interest.

In this paper, we show that there is a family of polynomials P_n, where P_n is a polynomial in n variables of degree at most d = O(log^2(n)), such that * P_n can be computed by linear sized homogeneous depth-5 arithmetic circuits, * P_n can be computed by poly(n) sized non-homogeneous depth-3 arithmetic circuits. * Any homogeneous depth-4 arithmetic circuit computing P_n must have size at least n^{Omega(sqrt(d))}. This shows that the parameters for the depth reduction results of [Agrawal-Vinay 08, Koiran 12, Tavenas 13] are tight for extremely restricted classes of arithmetic circuits, for instance homogeneous depth-5 circuits and non-homogeneous depth-3 circuits, and over an appropriate range of parameters, qualitatively improve a result of [Kumar-Saraf 14], which showed that the parameters of depth reductions are optimal for algebraic branching programs. As an added advantage, our proofs are much shorter and simpler than the two known proofs of n^{Omega(sqrt(d))} lower bound for homogeneous depth-4 circuits [Kayal-Limaye-Saha-Srinivasan 14, Kumar-Saraf 14], albeit our proofs only work when d = O(log^2(n)).

In recent years, a very exciting and promising method for proving lower bounds for arithmetic circuits has been proposed. This method combines the method of depth reduction developed in the works of Agrawal and Vinay [FOCS, IEEE, Piscataway, NJ, 2008, pp. 67--75], Koiran [Theoret. Comput. Sci., 448 (2012), pp. 56--65], and Tavenas [Inform. and Comput., 240 (2015), pp, 2--11], and the use of the shifted partial derivative complexity measure developed in the works of Kayal [Electronic Colloquium on Computational Complexity, TR12-081, 2012] and Gupta et al. [J. ACM, 61 (2014), 33]. These results inspired a flurry of other beautiful results and strong lower bounds for various classes of arithmetic circuits, in particular a recent work of Kayal, Saha, and Saptharishi [STOC, ACM, New York, 2014, pp. 146--153] showing superpolynomial lower bounds for regular arithmetic formulas via an improved depth reduction for these formulas. It was left as an intriguing question if these methods could prove superpolynomial lower bounds for general (homogeneous) arithmetic formulas, and if so this would indeed be a breakthrough in arithmetic circuit complexity. In this paper we study the power and limitations of depth reduction and shifted partial derivatives for arithmetic formulas. We do it via studying the class of depth 4 homogeneous arithmetic circuits. We show: (1) the first superpolynomial lower bounds for the class of homogeneous depth 4 circuits with top fan-in $o(\log n)$. The core of our result is to show improved depth reduction for these circuits. This class of circuits has received much attention for the problem of polynomial identity testing. We give the first nontrivial lower bounds for these circuits for any top fan-in $\geq 2$. (2) We show that improved depth reduction is not possible when the top fan-in is $\Omega(\log n)$. In particular this shows that the depth reduction procedure of Koiran [Theoret. Comput. Sci., 448 (2012), pp. 56--65] and Tavenas [Inform. and Comput., 240 (2012), pp, 2--11] cannot be improved even for homogeneous formulas, thus strengthening the results of Fournier et al. [SIAM J. Comput., 44 (2015), pp, 1173--1201] who showed that depth reduction is tight for circuits, and answering some of the main open questions of [N. Kayal, C. Saha, and R. Saptharishi, STOC, ACM, New York, 2014, pp. 146--153] and [H. Fournier et al. SIAM J. Comput., 44 (2015), pp, 1173--1201]. Our results in particular suggest that the method of improved depth reduction and shifted partial derivatives may not be powerful enough to prove superpolynomial lower bounds for (even homogeneous) arithmetic formulas.

We prove exponential lower bounds on the size of homogeneous depth 4 arithmetic circuits computing an explicit polynomial in VP. Our results hold for the Iterated Matrix Multiplication polynomial - in particular we show that any homogeneous depth 4 circuit computing the (1, 1) entry in the product of n generic matrices of dimension nO(1)must have size nΩ(√n). Our results strengthen previous works in two significant ways. 1) Our lower bounds hold for a polynomial in VP. Prior to our work, Kayal et al [KLSSa] proved an exponential lower bound for homogeneous depth 4 circuits (over fields of characteristic zero) computing a poly in VNP. The best known lower bounds for a depth 4 homogeneous circuit computing a poly in VP was the bound of nΩ(log n)by [KLSSb], [KLSSa]. Our exponential lower bounds also give the first exponential separation between general arithmetic circuits and homogeneous depth 4 arithmetic circuits. In particular they imply that the depth reduction results of Koiran [Koi12] and Tavenas [Tav13] are tight even for reductions to general homogeneous depth 4 circuits (without the restriction of bounded bottom fanin). 2) Our lower bound holds over all fields. The lower bound of [KLSSa] worked only over fields of characteristic zero. Prior to our work, the best lower bound for homogeneous depth 4 circuits over fields of positive characteristic was nΩ(log n)[KLSSb], [KLSSa].

In recent years, a very exciting and promising method for proving lower bounds for arithmetic circuits has been proposed. This method combines the method of depth reduction developed in the works of Agrawal and Vinay[1], Koiran [11] and Tavenas [16], and the use of the shifted partial derivative complexity measure developed in the works of Kayal [9] and Gupta et al [5]. These results inspired a flurry of other beautiful results and strong lower bounds for various classes of arithmetic circuits, in particular a recent work of Kayal et al [10] showing superpolynomial lower bounds for regular arithmetic formulas via an improved depth reduction for these formulas. It was left as an intriguing question if these methods could prove superpolynomial lower bounds for general (homogeneous) arithmetic formulas, and if so this would indeed be a breakthrough in arithmetic circuit complexity. In this paper we study the power and limitations of depth reduction and shifted partial derivatives for arithmetic formulas. We do it via studying the class of depth 4 homogeneous arithmetic circuits. We show: (1) the first superpolynomial lower bounds for the class of homogeneous depth 4 circuits with top fan-in o(log n). The core of our result is to show improved depth reduction for these circuits. This class of circuits has received much attention for the problem of polynomial identity testing. We give the first nontrivial lower bounds for these circuits for any top fan-in ≥ 2. (2) We show that improved depth reduction is not possible when the top fan-in is Ω(log n). In particular this shows that the depth reduction procedure of Koiran and Tavenas [11, 16] cannot be improved even for homogeneous formulas, thus strengthening the results of Fournier et al [3] who showed that depth reduction is tight for circuits, and answering some of the main open questions of [10, 3]. Our results in particular suggest that the method of improved depth reduction and shifted partial derivatives may not be powerful enough to prove superpolynomial lower bounds for (even homogeneous) arithmetic formulas.