It is a long-standing open problem in algebraic complexity to prove lower bounds against multilinear algebraic branching programs (mlABPs), however the best lower bounds are still quadratic (Alon, Kumar and Volk (Combinatorica 2020)). At the same time, it remains a possibility that the "min-partition rank" method introduced by Raz (Theory Comput. 2006), which is used to prove all known multilinear lower bounds, can also be used to prove superpolynomial lower bounds on the size of mlABPs. In this paper, we analyze the potential of the min-partition rank method to prove lower bounds on the size of mlABPs, and show the following results: 1) We relate this method to a purely combinatorial question regarding the minimum size of set systems whose chains satisfy a discrepancy condition. In the case of set-multilinear ABPs, this combinatorial measure characterizes the best lower bound that can be achieved via the min-partition rank method. 2) We prove a non-trivial upper bound on the size of a set system satisfying this combinatorial property. Together with our construction of full-rank mlABPs from set systems, this recovers a superpolynomial separation between mlABPs and multilinear formulas (Dvir, Malod, Perifel and Yehudayoff (STOC 2012)) via a conceptually different proof. 3) The property we study extends combinatorial notions of "balancing sets" considered in previous works, for which near-tight bounds are known via intervals families. We show that any intervals set system is very far from satisfying our property. This showcases how our methods capture combinatorial structures that evade previous techniques, and also allows us to improve and generalize known lower bounds for sum of ordered set-multilinear ABPs (Chatterjee, Kush, Saraf, Shpilka (CCC 2024)). These results build a bridge between algebraic complexity theory and the behavior of random walks. Our upper bound uses the fact that, with noticeable probability, a random walk of length n on the integers returns to its starting point at least once every n/log n steps (Csáki, Erdős, and Révész (PTRF 1985)), while, for our lower bound, we prove that two independent random walks are "far" from each other in discrete Fréchet distance.

We investigate the closure properties of read-once oblivious Algebraic Branching Programs (roABPs) under various natural algebraic operations and prove the following. - Non-closure under factoring: There is a sequence of explicit polynomials (f_n(x₁,…, x_n))_n that have poly(n)-sized roABPs such that some irreducible factor of f_n requires roABPs of superpolynomial size in any order. - Non-closure under powering: There is a sequence of polynomials (f_n(x₁,…, x_n))_n with poly(n)-sized roABPs such that any super-constant power of f_n does not have roABPs of polynomial size in any order (and f_nⁿ requires exponential size in any order). - Non-closure under symmetric operations: There are symmetric polynomials (f_n(e₁,…, e_n))_n that have roABPs of polynomial size such that f_n(x₁,…, x_n) do not have roABPs of subexponential size. (Here, e₁,…, e_n denote the elementary symmetric polynomials in n variables.) These results should be viewed in light of known results on models such as algebraic circuits, (general) algebraic branching programs, formulas and constant-depth circuits, all of which are known to be closed under these operations. To prove non-closure under factoring, we construct hard polynomials based on expander graphs using gadgets that lift their hardness from sparse polynomials to roABPs. For symmetric compositions, we show that the circulant polynomial requires roABPs of exponential size in every variable order.

All known proofs of the PCP theorem rely on multiple ”composition” steps, where PCPs over large alphabets are turned into PCPs over much smaller alphabets at a (relatively) small price in the soundness error of the PCP. Algebraic proofs, starting with the work of Arora, Lund, Motwani, Sudan, and Szegedy use at least 2 such composition steps, whereas the ”Gap amplification” proof of Dinur uses Θ(logn) such composition steps. In this work, we present the first PCP construction using just one composition step. The key ingredient, missing in previous work and finally supplied in this paper, is a basic PCP (of Proximity) of size 2nε, for any ε > 0, that makes Oε(1) queries.

We study the power of negation in the Boolean and algebraic settings and show the following results.

It is a well-known fact that the permanent polynomial is complete for the complexity class VNP, and it is largely suspected that the determinant does not share this property, despite its similar expression. We study the question of why the VNP-completeness proof of the permanent fails for the determinant. We isolate three fundamental properties that are sufficient to prove a polynomial sequence is VNP-hard, of which two are shared by both the permanent and the determinant. We proceed to show that the permanent satisfies the third property, which we refer to as the "cost of a boolean sum", while the determinant does not, showcasing the fundamental difference between the polynomial families. We further note that this differentiation also applies in the border complexity setting and that our results apply for counting complexity.

The celebrated Ore-DeMillo-Lipton-Schwartz-Zippel (ODLSZ) lemma asserts that n-variate non-zero polynomial functions of degree d over a field 𝔽, are non-zero over any "grid" (points of the form Sⁿ for finite subset S ⊆ 𝔽) with probability at least max{|S|^{-d/(|S|-1)},1-d/|S|} over the choice of random point from the grid. In particular, over the Boolean cube (S = {0,1} ⊆ 𝔽), the lemma asserts non-zero polynomials are non-zero with probability at least 2^{-d}. In this work we extend the ODLSZ lemma optimally (up to lower-order terms) to "Boolean slices" i.e., points of Hamming weight exactly k. We show that non-zero polynomials on the slice are non-zero with probability (t/n)^{d}(1 - o_{n}(1)) where t = min{k,n-k} for every d ≤ k ≤ (n-d). As with the ODLSZ lemma, our results extend to polynomials over Abelian groups. This bound is tight upto the error term as evidenced by multilinear monomials of degree d, and it is also the case that some corrective term is necessary. A particularly interesting case is the "balanced slice" (k = n/2) where our lemma asserts that non-zero polynomials are non-zero with roughly the same probability on the slice as on the whole cube. The behaviour of low-degree polynomials over Boolean slices has received much attention in recent years. However, the problem of proving a tight version of the ODLSZ lemma does not seem to have been considered before, except for a recent work of Amireddy, Behera, Paraashar, Srinivasan and Sudan (SODA 2025), who established a sub-optimal bound of approximately ((k/n)⋅ (1-(k/n)))^d using a proof similar to that of the standard ODLSZ lemma. While the statement of our result mimics that of the ODLSZ lemma, our proof is significantly more intricate and involves spectral reasoning which is employed to show that a natural way of embedding a copy of the Boolean cube inside a balanced Boolean slice is a good sampler.

There is a large body of work that shows how to leverage lower bound techniques for circuit classes to obtain satisfiability algorithms that run in better than brute-force time [24, 38]. For circuits with threshold gates, there are several such algorithms based on either Probabilistic Representations by low-degree polynomials, which allow for the use of fast polynomial evaluation algorithms, or Low rank, which allows for an efficient reduction to rectangular matrix multiplication. In this paper, we use a related notion of probabilistic rank to obtain satisfiability algorithms for circuit classes contained in ACC0 ◦ 3-PTF, i.e. constant-depth circuits with modular counting gates and a single layer of degree-3 polynomial threshold functions. Even for the special case of a single 3-PTF, it is not clear how to use either of the above two strategies to get a non-trivial satisfiability algorithm. The best known algorithm in this case previously was based on memoization and yields worse guarantees than our algorithm.

In this work, we show that the class of multivariate degree-d polynomials mapping {0,1}n to any Abelian group G is locally correctable with Õd((log n )d) queries for up to a fraction of errors approaching half the minimum distance of the underlying code. In particular, this result holds even for polynomials over the reals or the rationals, special cases that were previously not known. Further, we show that they are locally list correctable up to a fraction of errors approaching the minimum distance of the code. These results build on and extend the prior work of Amireddy, Behera, Paraashar, Srinivasan, and Sudan [1] (STOC 2024) who considered the case of linear polynomials (d = 1) and gave analogous results.

We consider the task of locally correcting, and locally list-correcting, multivariate linear functions over the domain {0,1}n over arbitrary fields and more generally Abelian groups. Such functions form error-correcting codes of relative distance 1/2 and we give local-correction algorithms correcting up to nearly 1/4-fraction errors making O(logn) queries. This query complexity is optimal up to poly(loglogn) factors. We also give local list-correcting algorithms correcting (1/2 − ε)-fraction errors with Oε(logn) queries. These results may be viewed as natural generalizations of the classical work of Goldreich and Levin whose work addresses the special case where the underlying group is ℤ2. By extending to the case where the underlying group is, say, the reals, we give the first non-trivial locally correctable codes (LCCs) over the reals (with query complexity being sublinear in the dimension (also known as message length)). Previous works in the area mostly focused on the case where the domain is a vector space or a group and this lends to tools that exploit symmetry. Since our domains lack such symmetries, we encounter new challenges whose resolution may be of independent interest. The central challenge in constructing the local corrector is constructing “nearly balanced vectors” over {−1,1}n that span 1n — we show how to construct O(logn) vectors that do so, with entries in each vector summing to ±1. The challenge to the local-list-correction algorithms, given the local corrector, is principally combinatorial, i.e., in proving that the number of linear functions within any Hamming ball of radius (1/2−ε) is Oε(1). Getting this general result covering every Abelian group requires integrating a variety of known methods with some new combinatorial ingredients analyzing the structural properties of codewords that lie within small Hamming balls.

Proving explicit lower bounds on the size of algebraic formulas is a long-standing open problem in the area of algebraic complexity theory. Recent results in the area (e.g. a lower bound against constant-depth algebraic formulas due to Limaye, Srinivasan, and Tavenas (FOCS 2021)) have indicated a way forward for attacking this question: show that we can convert a general algebraic formula to a homogeneous algebraic formula with moderate blow-up in size, and prove strong lower bounds against the latter model. Here, a homogeneous algebraic formula F for a polynomial P is a formula in which all subformulas compute homogeneous polynomials. In particular, if P is homogeneous of degree d, F does not contain subformulas that compute polynomials of degree greater than d. We investigate the feasibility of the above strategy and prove a number of positive and negative results in this direction.

We study the question of local testability of low (constant) degree functions from a product domain 𝒮_1 × … × 𝒮_n to a field 𝔽, where 𝒮_i ⊆ 𝔽 can be arbitrary constant sized sets. We show that this family is locally testable when the grid is "symmetric". That is, if 𝒮_i = 𝒮 for all i, there is a probabilistic algorithm using constantly many queries that distinguishes whether f has a polynomial representation of degree at most d or is Ω(1)-far from having this property. In contrast, we show that there exist asymmetric grids with |𝒮_1| = ⋯ = |𝒮_n| = 3 for which testing requires ω_n(1) queries, thereby establishing that even in the context of polynomials, local testing depends on the structure of the domain and not just the distance of the underlying code. The low-degree testing problem has been studied extensively over the years and a wide variety of tools have been applied to propose and analyze tests. Our work introduces yet another new connection in this rich field, by building low-degree tests out of tests for "junta-degrees". A function f:𝒮_1 × ⋯ × 𝒮_n → 𝒢, for an abelian group 𝒢 is said to be a junta-degree-d function if it is a sum of d-juntas. We derive our low-degree test by giving a new local test for junta-degree-d functions. For the analysis of our tests, we deduce a small-set expansion theorem for spherical/hamming noise over large grids, which may be of independent interest.

Classical results of Brent, Kuck and Maruyama (IEEE Trans.Computers 1973) and Brent (JACM 1974) show that any algebraic formula of size s can be converted to one of depth Oplog sq with only a polynomial blow-up in size.In this paper, we consider a fine-grained version of this result depending on the degree of the polynomial computed by the algebraic formula.Given a homogeneous algebraic formula of size s computing a polynomial P of degree d, we show that P can also be computed by an (unbounded fan-in) algebraic formula of depth Oplog dq and size polypsq.Our proof shows that this result also holds in the highly restricted setting of monotone, non-commutative algebraic formulas.This improves on previous results in the regime when d is small (i.e., d " s op1q ).In particular, for the setting of d " Oplog sq, along with a result of Raz (STOC 2010, JACM 2013), our result implies the same depth reduction even for inhomogeneous formulas.This is particularly interesting in light of recent algebraic formula lower bounds, which work precisely in this "low-degree" and "low-depth" setting.We also show that these results cannot be improved in the monotone setting, even for commutative formulas.

The δ-Coin Problem is the problem of distinguishing between a sequence of coin tosses that come up Heads with probability either 1+δ/2 or 1−δ/2. The computational complexity of this problem in various models has been studied in many previous works with various applications related to derandomization, hierarchy theorems, cryptography and meta-complexity.

We study the following natural question on random sets of points in 𝔽₂^m: Given a random set of k points Z = {z₁, z₂, … , z_k} ⊆ 𝔽₂^m, what is the dimension of the space of degree at most r multilinear polynomials that vanish on all points in Z? We show that, for r ≤ γ m (where γ > 0 is a small, absolute constant) and k = (1-ε)⋅binom(m, ≤ r) for any constant ε > 0, the space of degree at most r multilinear polynomials vanishing on a random set Z = {z_1,…, z_k} has dimension exactly binom(m, ≤ r) - k with probability 1 - o(1). This bound shows that random sets have a much smaller space of degree at most r multilinear polynomials vanishing on them, compared to the worst-case bound (due to Wei (IEEE Trans. Inform. Theory, 1991)) of binom(m, ≤ r) - binom(log₂ k, ≤ r) ≫ binom(m, ≤ r) - k. Using this bound, we show that high-degree Reed-Muller codes (RM(m,d) with d > (1-γ) m) "achieve capacity" under the Binary Erasure Channel in the sense that, for any ε > 0, we can recover from (1-ε)⋅binom(m, ≤ m-d-1) random erasures with probability 1 - o(1). This also implies that RM(m,d) is also efficiently decodable from ≈ binom(m, ≤ m-(d/2)) random errors for the same range of parameters.

In the algebraic metacomplexity framework we prove that the decomposition of metapolynomials into their isotypic components can be implemented efficiently, namely with only a quasipolynomial blowup in the circuit size. We use this to resolve an open question posed by Grochow, Kumar, Saks & Saraf (2017). Our result means that many existing algebraic complexity lower bound proofs can be efficiently converted into isotypic lower bound proofs via highest weight metapolynomials, a notion studied in geometric complexity theory. In the context of algebraic natural proofs, it means that without loss of generality algebraic natural proofs can be assumed to be isotypic. Our proof is built on the Poincaré-Birkhoff-Witt theorem for Lie algebras and on Gelfand-Tsetlin theory, for which we give the necessary comprehensive background.

A polynomial P ∈ 𝔽[x_1,…,x_n] is said to be symmetric if it is invariant under any permutation of its input variables. The study of symmetric polynomials is a classical topic in mathematics, specifically in algebraic combinatorics and representation theory. More recently, they have been studied in several works in computer science, especially in algebraic complexity theory. In this paper, we prove the computational hardness of one of the most basic kinds of symmetric polynomials: the monomial symmetric polynomials, which are obtained by summing all distinct permutations of a single monomial. This family of symmetric functions is a natural basis for the space of symmetric polynomials (over any field), and generalizes many well-studied families such as the elementary symmetric polynomials and the power-sum symmetric polynomials. We show that certain families of monomial symmetric polynomials are VNP-complete with respect to oracle reductions. This stands in stark contrast to the case of elementary and power symmetric polynomials, both of which have constant-depth circuits of polynomial size.

An Algebraic Formula for a polynomial P∈ [x1,…,xN] is an algebraic expression for P(x1,…,xN) using variables, field constants, additions and multiplications. Such formulas capture an algebraic analog of the Boolean complexity class NC1. Proving lower bounds against this model is thus an important problem.

Nisan and Szegedy (CC 1994) showed that any Boolean function f:{0,1}ⁿ → {0,1} that depends on all its input variables, when represented as a real-valued multivariate polynomial P(x₁,…,x_n), has degree at least log n - O(log log n). This was improved to a tight (log n - O(1)) bound by Chiarelli, Hatami and Saks (Combinatorica 2020). Similar statements are also known for other Boolean function complexity measures such as Sensitivity (Simon (FCT 1983)), Quantum query complexity, and Approximate degree (Ambainis and de Wolf (CC 2014)). In this paper, we address this question for Probabilistic degree. The function f has probabilistic degree at most d if there is a random real-valued polynomial of degree at most d that agrees with f at each input with high probability. Our understanding of this complexity measure is significantly weaker than those above: for instance, we do not even know the probabilistic degree of the OR function, the best-known bounds put it between (log n)^{1/2-o(1)} and O(log n) (Beigel, Reingold, Spielman (STOC 1991); Tarui (TCS 1993); Harsha, Srinivasan (RSA 2019)). Here we can give a near-optimal understanding of the probabilistic degree of n-variate functions f, modulo our lack of understanding of the probabilistic degree of OR. We show that if the probabilistic degree of OR is (log n)^c, then the minimum possible probabilistic degree of such an f is at least (log n)^{c/(c+1)-o(1)}, and we show this is tight up to (log n)^{o(1)} factors.

An Algebraic Circuit for a polynomial$P\ \ \in \mathbb{F}[x_{1}, \ldots, x_{N}]$is a computational model for constructing the polynomial$P$using only additions and multiplications. It is a syntactic model of computation, as opposed to the Boolean Circuit model, and hence lower bounds for this model are widely expected to be easier to prove than lower bounds for Boolean circuits. Despite this, we do not have superpolynomial lower bounds against general algebraic circuits of depth 3 (except over constant-sized finite fields) and depth 4 (over fields other than$\mathbb{F}_{2}$), while constant-depth Boolean circuit lower bounds have been known since the early 1980s. In this paper, we prove the first super polynomial lower bounds against general algebraic circuits of all constant depths over all fields of characteristic 0 (or large). We also prove the first lower bounds against homogeneous algebraic circuits of constant depth over any field. Our approach is surprisingly simple. We first prove superpolynomial lower bounds for constant-depth Set-Multilinear circuits. While strong lower bounds were already known against such circuits, most previous lower bounds were of the form$f(d)\cdot \text{poly}(N)$, where$d$denotes the degree of the polynomial. In analogy with Parameterized complexity, we call this an FPT lower bound. We extend a well-known technique of Nisan and Wigderson (FOCS 1995) to prove non-FPT lower bounds against constant-depth set-multilinear circuits computing the Iterated Matrix Multiplication polynomial$\text{IMM}_{n, d}$(which computes a fixed entry of the product of$d\ n\times n$matrices). More precisely, we prove that any set-multilinear circuit of depth$\Delta$computing$\text{IMM}_{n, d}$must have size at least$n^{d^{\exp(-O(\Delta))}}$. This result holds over any field, as long as$d=o(\log n)$. We then show how to convert any constant-depth algebraic circuit of size$s$to a constant-depth set-multilinear circuit with a blow-up in size that is exponential in$d$but only polynomial in$s$over fields of characteristic 0. (For depths greater than 3, previous results of this form increased the depth of the resulting circuit to$\Omega(\log s))$. This implies our constant-depth circuit lower bounds. Finally, we observe that our superpolynomial lower bound for constant-depth circuits implies the first deterministic sub-exponential time algorithm for solving the Polynomial Identity Testing (PIT) problem for all small depth circuits using the known connection between algebraic hardness and randomness.

In this paper, we prove the first fixed-depth size-hierarchy theorem for uniform ${\mathrm{AC}}^0[\oplus]$. In particular, we show that for any fixed $d$ and integer parameter $k$, the class ${\mathcal{{C}}}_{d,k}$ of functions that have uniform ${\mathrm{AC}}^0[\oplus]$ formulas of depth $d$ and size $n^k$ form an infinite hierarchy. We show this by exhibiting the first class of functions that have uniform ${\mathrm{AC}}^0[\oplus]$ formulas of size $n^k$ but no ${\mathrm{AC}}^0[\oplus]$ formulas of size less than $n^{\varepsilon_0 k}$ for some absolute constant $\varepsilon_0 > 0$. The uniform formulas are designed to solve the $\delta$-coin problem, which is the computational problem of distinguishing between coins that are heads with probability $(1+\delta)/2$ or $(1-\delta)/2,$ where $\delta$ is a parameter that is going to $0$. We study the complexity of this problem and make progress on both upper bound and lower bound fronts. Regarding Upper bounds, for any constant $d\geq 2$, we show that there are uniform monotone ${\mathrm{AC}}^0$ formulas (i.e., made up of AND and OR gates only) solving the $\delta$-coin problem that have depth $d$, size $\exp(O(d\cdot(1/\delta)^{1/(d-1)}))$, and sample complexity (i.e., number of inputs) ${\mathop{\mathrm{poly}}}(1/\delta).$ This matches previous upper bounds of O'Donnell and Wimmer [ICALP 2007: Automata, Languages and Programming, Lecture Notes in Comput. Sci. 4596, Springer, New York, 2007, pp. 195--206] and Amano [ICALP 2009: Automata, Languages and Programming, Lecture Notes in Comput. Sci. 5555, Springer, New York, 2009, pp. 59--70] in terms of size (which is optimal), while improving the sample complexity from $\exp(O(d\cdot(1/\delta)^{1/(d-1)}))$ to ${\mathop{\mathrm{poly}}}(1/\delta)$. The improved sample complexity is crucial for proving the size-hierarchy theorem. Regarding Lower bounds, we show that the preceding upper bounds are nearly tight (in terms of size) even for the significantly stronger model of ${\mathrm{AC}}^0[\oplus]$ formulas (which are also allowed NOT and Parity gates): formally, we show that any ${\mathrm{AC}}^0[\oplus]$ formula solving the $\delta$-coin problem must have size $\exp(\Omega(d\cdot(1/\delta)^{1/(d-1)})).$ This strengthens a result of Shaltiel and Viola [SIAM J. Comput., 39 (2010), pp. 3122--3154], who prove an $\exp(\Omega((1/\delta)^{1/(d+2)}))$ lower bound for ${\mathrm{AC}}^0[\oplus]$ circuits, and a result of Cohen, Ganor, and Raz [APPROX-RANDOM, LIPIcs. Leibniz Int. Proc. Inform. 28, Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik, Wadern, 2014, pp. 618--629], who show an $\exp(\Omega((1/\delta)^{1/(d-1)}))$ lower bound for ${\mathrm{AC}}^0$ circuits. The upper bound is a derandomization involving a use of Janson's inequality and an extension of classical polynomial-based combinatorial designs. For the lower bound, we prove an optimal (up to a constant factor) degree lower bound for multivariate polynomials over ${\mathbb{F}}_2$ solving the $\delta$-coin problem, which may be of independent interest.

The probabilistic degree of a Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is defined to be the smallest $d$ such that there is a random polynomial ${P}$ of degree at most $d$ that agrees with $f$ at each point with high probability. Introduced by Razborov [ Mat. Zametki, 41 (1987), pp. 598--607], upper and lower bounds on probabilistic degrees of Boolean functions---specifically symmetric Boolean functions---have been used to prove explicit lower bounds, design pseudorandom generators, and devise algorithms for combinatorial problems. In this paper, we characterize the probabilistic degrees of all symmetric Boolean functions up to polylogarithmic factors over all fields of fixed characteristic (positive or zero).

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.

Hegedűs’s lemma is the following combinatorial statement regarding polynomials over finite fields. Over a field F of characteristic p > 0 and for q a power of p, the lemma says that any multilinear polynomial P∈ F[x 1,…,x n ] of degree less than q that vanishes at all points in {0,1} n of Hamming weight k∈ [q,n−q] must also vanish at all points in {0,1} n of weight k + q. This lemma was used by Hegedűs (2009) to give a solution to Galvin’s problem, an extremal problem about set systems; by Alon, Kumar and Volk (2018) to improve the best-known multilinear circuit lower bounds; and by Hrubeš, Ramamoorthy, Rao and Yehudayoff (2019) to prove optimal lower bounds against depth-2 threshold circuits for computing some symmetric functions. In this paper, we formulate a robust version of Hegedűs’s lemma. Informally, this version says that if a polynomial of degree o(q) vanishes at most points of weight k, then it vanishes at many points of weight k+q. We prove this lemma and give the following three different applications.

We study the complexity of computing symmetric and threshold functions by constant-depth circuits with Parity gates, also known as AC^0[oplus] circuits. Razborov [Alexander A. Razborov, 1987] and Smolensky [Roman Smolensky, 1987; Roman Smolensky, 1993] showed that Majority requires depth-d AC^0[oplus] circuits of size 2^{Omega(n^{1/2(d-1)})}. By using a divide-and-conquer approach, it is easy to show that Majority can be computed with depth-d AC^0[oplus] circuits of size 2^{O~(n^{1/(d-1)})}. This gap between upper and lower bounds has stood for nearly three decades. Somewhat surprisingly, we show that neither the upper bound nor the lower bound above is tight for large d. We show for d >= 5 that any symmetric function can be computed with depth-d AC^0[oplus] circuits of size exp(O~(n^{2/3 * 1/(d-4)})). Our upper bound extends to threshold functions (with a constant additive loss in the denominator of the double exponent). We improve the Razborov-Smolensky lower bound to show that for d >= 3 Majority requires depth-d AC^0[oplus] circuits of size 2^{Omega(n^{1/(2d-4)})}. For depths d <= 4, we are able to refine our techniques to get almost-optimal bounds: the depth-3 AC^0[oplus] circuit size of Majority is 2^{Theta~(n^{1/2})}, while its depth-4 AC^0[oplus] circuit size is 2^{Theta~(n^{1/4})}.

In this paper we prove two results about AC^0[oplus] circuits. (1) We show that for d(N) = o(sqrt(log N/log log N)) and N <= s(N) <= 2^(dN^(1/4d^2)) there is an explicit family of functions {f_N:{0,1}^N - > {0,1}} such that - f_N has uniform AC^0 formulas of depth d and size at most s; - f_N does not have AC^0[oplus] formulas of depth d and size s^epsilon, where epsilon is a fixed absolute constant. This gives a quantitative improvement on the recent result of Limaye, Srinivasan, Sreenivasaiah, Tripathi, and Venkitesh, (STOC, 2019), which proved a similar Fixed-Depth Size-Hierarchy theorem but for d << log log N and s << exp(N^(1/2^Omega(d))). As in the previous result, we use the Coin Problem to prove our hierarchy theorem. Our main technical result is the construction of uniform size-optimal formulas for solving the coin problem with improved sample complexity (1/delta)^O(d) (down from (1/delta)^(2^O(d)) in the previous result). (2) In our second result, we show that randomness buys depth in the AC^0[oplus] setting. Formally, we show that for any fixed constant d >= 2, there is a family of Boolean functions that has polynomial-sized randomized uniform AC^0 circuits of depth d but no polynomial-sized (deterministic) AC^0[oplus] circuits of depth d. Previously Viola (Computational Complexity, 2014) showed that an increase in depth (by at least 2) is essential to avoid superpolynomial blow-up while derandomizing randomized AC^0 circuits. We show that an increase in depth (by at least 1) is essential even for AC^0[oplus]. As in Viola’s result, the separating examples are promise variants of the Majority function on N inputs that accept inputs of weight at least N/2 + N/(log N)^(d-1) and reject inputs of weight at most N/2 - N/(log N)^(d-1).

Proving super-polynomial size lower bounds for $\textsf{TC}^0$, the class of constant-depth, polynomial-size circuits of Majority gates, is a notorious open problem in complexity theory. A major frontier is to prove that $\textsf{NEXP}$ does not have poly-size $\textsf{THR} \circ \textsf{THR}$ circuit (depth-two circuits with linear threshold gates). In recent years, R.~Williams proposed a program to prove circuit lower bounds via improved algorithms. In this paper, following Williams' framework, we show that the above frontier question can be resolved by devising slightly faster algorithms for several fundamental problems: 1. Shaving Logs for $\textsf{$\ell_2$-Furthest-Pair}$. An $n^2 \textrm{poly}(d) / \log^{ω(1)} n$ time algorithm for $\textsf{$\ell_2$-Furthest-Pair}$ in $\mathbb{R}^d$ for polylogarithmic $d$ implies $\textsf{NEXP}$ has no polynomial size $\textsf{THR} \circ \textsf{THR}$ circuits. The same holds for Hopcroft's problem, $\textsf{Bichrom.-$\ell_2$-Closest-Pair}$ and Integer $\textsf{Max-IP}$. 2. Shaving Logs for Approximate $\textsf{Bichrom.-$\ell_2$-Closest-Pair}$. An $n^2 \textrm(d) / \log^{ω(1)} n$ time algorithm for $(1+1/\log^{ω(1)} n)$-approximation to $\textsf{Bichrom.-$\ell_2$-Closest-Pair}$ or $\textsf{Bichrom.-$\ell_1$-Closest-Pair}$ for polylogarithmic $d$ implies $\textsf{NEXP}$ has no polynomial size $\textsf{SYM}\circ\textsf{THR}$ circuits. 3. Shaving Logs for Modest Dimension Boolean $\textsf{Max-IP}$. An $n^2 / \log^{ω(1)} n$ time algorithm for Bichromatic Maximum Inner Product with vector dimension $d = n^ε$ for any small constant $ε$ would imply $\textsf{NEXP}$ has no polynomial size $\textsf{THR} \circ \textsf{THR}$ circuits. Note there is an $n^2\textrm{polylog}(n)$ time algorithm via fast rectangle matrix multiplication. Our results build on two structure lemmas for threshold circuits.

In this work we prove the first Fixed-depth Size-Hierarchy Theorem for uniform AC0[⊕]. In particular, we show that for any fixed d, the class Cd,k of functions that have uniform AC0[⊕] formulas of depth d and size nk form an infinite hierarchy. We show this by exhibiting the first class of explicit functions where we have nearly (up to a polynomial factor) matching upper and lower bounds for the class of AC0[⊕] formulas.

We investigate the power of Non-commutative Arithmetic Circuits , which compute polynomials over the free non-commutative polynomial ring \({\mathbb{F}\langle{x_1,\ldots,x_N\rangle}}\) , where variables do not commute. We consider circuits that are restricted in the ways in which they can compute monomials: this can be seen as restricting the families of parse trees that appear in the circuit. Such restrictions capture essentially all non-commutative circuit models for which lower bounds are known. We prove several results about such circuits. We show exponential lower bounds for circuits with up to an exponential number of parse trees, strengthening the work of Lagarde et al . [Electronic Colloquium on Comput Complexity (ECCC) vol 23, no 94, 2016 ], who prove such a result for Unique Parse Tree (UPT) circuits which have a single parse tree. The polynomial we prove a lower bound for is in fact computable by a polynomial-sized non-commutative circuit. We show exponential lower bounds for circuits whose parse trees are rotations of a single tree. This simultaneously generalizes recent lower bounds of Limaye et al . (Theory Comput 12(1):1–38, 2016 ) and the above lower bounds of Lagarde et al . ( 2016 ), which are known to be incomparable. Here too, the hard polynomial is computable by a polynomial-sized non-commutative circuit. We make progress on a question of Nisan (STOC, pp 410–418, 1991 ) regarding separating the power of Algebraic Branching Programs (ABPs) and Formulas in the non-commutative setting by showing a tight lower bound of \({n^{\Omega(\log d)}}\) for any UPT formula computing the product of d \({n \times n}\) matrices. When \({d \leq \log n}\) , we can also prove superpolynomial lower bounds for formulas with up to \({2^{o(d)}}\) many parse trees (for computing the same polynomial). Improving this bound to allow for \({2^{o(d)}}\) trees would give an unconditional separation between ABPs and Formulas. We give deterministic whitebox PIT algorithms for UPT circuits over any field, strengthening a result of Lagarde et al . ( 2016 ), and also for sums of a constant number of UPT circuits with different parse trees.

The complexity of Iterated Matrix Multiplication (IMM) is a central theme in Computational Complexity theory, as the problem is closely related to the problem of separating various complexity classes within ${P}$. In this paper, we study the algebraic formula complexity of multiplying $d$ many $2\times 2$ matrices, denoted ${IMM}_{d}$, and show that the well-known divide-and-conquer algorithm cannot be significantly improved at any depth as long as the formulas are multilinear. Formally, for each depth $\Delta \leq \log d$, we show that any product-depth $\Delta$ multilinear formula for ${IMM}_d$ must have size $\exp(\Omega(\Delta d^{1/\Delta})).$ It also follows from this that any multilinear circuit of product-depth $\Delta$ for the same polynomial of the above form must have a size of $\exp(\Omega(d^{1/\Delta})).$ In particular, any polynomial-sized multilinear formula for ${IMM}_d$ must have depth $\Omega(\log d)$, and any polynomial-sized multilinear circuit for ${IMM}_d$ must have depth $\Omega(\log d/\log \log d).$ Both of these bounds are tight up to constant factors. Our lower bound has the following three consequences for multilinear formula complexity. 1. Depth-reduction: A well-known result of Brent [ J. ACM, 21 (1974), pp. 201--206] implies that any formula of size $s$ can be converted to one of size $s^{O(1)}$ and depth $O(\log s)$; further, this reduction continues to hold for multilinear formulas. On the other hand, our lower bound implies that any depth-reduction in the multilinear setting cannot reduce the depth to $o(\log s)$ without a superpolynomial blow-up in size. 2. Circuits vs. formulas: Any circuit of size $s$ and product-depth $\Delta$ can be converted into a formula of product-depth $\Delta$ and size $s^{O(\Delta)}$. In the multilinear setting, we show that it is not possible to improve on this significantly for small depths. Formally, our results imply that for all large enough $s$ and $\Delta = o(\log s/\log \log s)$, there is an explicit multilinear polynomial $P_{s,\Delta}$ that has a syntactic multilinear circuit of size $s$ and is such that any multilinear formula of product-depth $\Delta$ computing $P_{s,\Delta}$ must have size $s^{\Omega(\Delta)}$. 3. Separations from general formulas: Shpilka and Yehudayoff [ Found. Trends Theor. Comput. Sci., 5 (2010), pp. 207--388] asked whether general formulas can be more efficient than multilinear formulas for computing multilinear polynomials. Our result, along with a nontrivial upper bound for ${IMM}_{d}$ implied by a result of Gupta et al. [SIAM J. Comput., 45 (2016), pp. 1064--1079], shows that for any size $s$ and product-depth $\Delta = o(\log s),$ general formulas of size $s$ and product-depth $\Delta$ cannot be converted to multilinear formulas of size $s^{O(1)}$ and product-depth $\Delta$ when the underlying field has characteristic zero.

We consider the following multiplication-based tests to check if a given function f : Fqn→ Fqis a codeword of the Reed-Muller code of dimension n and order d over the finite field Fqfor prime q (i.e., f is the evaluation of a degree-d polynomial over Fq for q prime). Teste,k: pick P1,..., Pkindependent random degree-e polynomials and accept if the function f P1· · · Pkis the evaluation of a degree-(d + ek) polynomial (i.e., is a codeword of the Reed-Muller code of dimension n and order (d + ek)). We prove the robust soundness of the abovementioned tests for large values of e, answering a question of Dinur and Guruswami. Previous soundness analyses of these tests were known only for the case when either e = 1 or k = 1. Even for the case k = 1 and e > 1, earlier soundness analyses were not robust. We also analyze a derandomized version of this test, where (for example) the polynomials P1, ..., Pkcan be the same random polynomial P. This generalizes a result of Guruswami et al. One of the key ingredients that go into the proof of this robust soundness is an extension of the standard Schwartz-Zippel lemma over general finite fields Fq, which may be of independent interest.

We study the size blow-up that is necessary to convert an algebraic circuit of product-depth Δ + 1 to one of product-depth Δ in the multilinear setting. We show that for every positive Δ = Δ(n) = o(log n/log log n), there is an explicit multilinear polynomial P(Δ) on n variables that can be computed by a multilinear formula of product-depth Δ + 1 and size O(n), but not by any multilinear circuit of product-depth Δ and size less than exp(nΩ(1/Δ)). This result is tight up to the constant implicit in the double exponent for all Δ = o(log n/log log n). This strengthens a result of Raz and Yehudayoff (Computational Complexity 2009) who prove a quasipolynomial separation for constant-depth multilinear circuits, and a result of Kayal, Nair and Saha (STACS 2016) who give an exponential separation in the case Δ = 1. Our separating examples may be viewed as algebraic analogues of variants of the Graph Reachability problem studied by Chen, Oliveira, Servedio and Tan (STOC 2016), who used them to prove lower bounds for constant-depth Boolean circuits.

We show explicit separations between the expressive powers of multilinear formulas of small-depth and all polynomial sizes. Formally, for any s = s(n) = n^{O(1)} and any delta>0, we construct explicit families of multilinear polynomials P_n in F[x_1,...,x_n] that have multilinear formulas of size s and depth three but no multilinear formulas of size s^{1/2-delta} and depth o(log n/log log n). As far as we know, this is the first such result for an algebraic model of computation. Our proof can be viewed as a derandomization of a lower bound technique of Raz (JACM 2009) using epsilon-biased spaces.

The well-known DeMillo-Lipton-Schwartz-Zippel lemma says that n-variate polynomials of total degree at most d over grids, i.e. sets of the form A_1 \times A_2 \times \cdots \times A_n, form error-correcting codes (of distance at least 2^{-d} provided \min_i\{|A_i|\}\geq 2). In this work we explore their local decodability and local testability. While these aspects have been studied extensively when A_1 = \cdots = A_n = \F_q are the same finite field, the setting when A_i's are not the full field does not seem to have been explored before. In this work we focus on the case A_i = {0,1} for every i. We show that for every field (finite or otherwise) there is a test whose query complexity depends only on the degree (and not on the number of variables). In contrast we show that decodability is possible over fields of positive characteristic (with query complexity growing with the degree of the polynomial and the characteristic), but not over the reals, where the query complexity must grow with $n$. As a consequence we get a natural example of a code (one with a transitive group of symmetries) that is locally testable but not locally decodable. Classical results on local decoding and testing of polynomials have relied on the 2-transitive symmetries of the space of low-degree polynomials (under affine transformations). Grids do not possess this symmetry: So we introduce some new techniques to overcome this handicap and in particular use the hypercontractivity of the (constant weight) noise operator on the Hamming cube.

We give a deterministic algorithm for counting the number of satisfying assignments of any AC^0[oplus] circuit C of size s and depth d over n variables in time 2^(n-f(n,s,d)), where f(n,s,d) = n/O(log(s))^(d-1), whenever s = 2^o(n^(1/d)). As a consequence, we get that for each d, there is a language in E^{NP} that does not have AC^0[oplus] circuits of size 2^o(n^(1/(d+1))). This is the first lower bound in E^{NP} against AC^0[oplus] circuits that beats the lower bound of 2^Omega(n^(1/2(d-1))) due to Razborov and Smolensky for large d. Both our algorithm and our lower bounds extend to AC^0[p] circuits for any prime p.

This paper gives the first separation between the power of formulas and circuits of equal depth in the AC^0[\oplus] basis (unbounded fan-in AND, OR, NOT and MOD_2 gates). We show, for all d(n) <= O(log n/log log n), that there exist polynomial-size depth-d circuits that are not equivalent to depth-d formulas of size n^{o(d)} (moreover, this is optimal in that n^{o(d)} cannot be improved to n^{O(d)}). This result is obtained by a combination of new lower and upper bounds for Approximate Majorities, the class of Boolean functions {0,1}^n to {0,1} that agree with the Majority function on 3/4 fraction of inputs. AC^0[\oplus] formula lower bound. We show that every depth-d AC^0[\oplus] formula of size s has a (1/8)-error polynomial approximation over F_2 of degree O((log s)/d)^{d-1}. This strengthens a classic $O(log s)^{d-1}$ degree approximation for circuits due to Razborov. Since the Majority function has approximate degree Theta(\sqrt n), this result implies an \exp(\Omega(dn^{1/2(d-1)})) lower bound on the depth-d AC^0[\oplus] formula size of all Approximate Majority functions for all d(n) <= O(log n). Monotone AC^0 circuit upper bound. For all d(n) <= O(log n/log log n), we give a randomized construction of depth-d monotone AC^0 circuits (without NOT or MOD_2 gates) of size \exp(O(n^{1/2(d-1)}))} that compute an Approximate Majority function. This strengthens a construction of formulas of size \exp(O(dn^{1/2(d-1)})) due to Amano.

In this paper we investigate the uniform distribution properties of polynomials in many variables and bounded degree over a fixed finite field F of prime order. Our main result is that a polynomial P : F^n -> F is poorly-distributed only if P is determined by the values of a few polynomials of lower degree, in which case we say that P has small rank. We give several applications of this result, paying particular attention to consequences for the theory of the so-called Gowers norms. We establish an inverse result for the Gowers U^{d+1}-norm of functions of the form f(x)= e_F(P(x)), where P : F^n -> F is a polynomial of degree less than F, showing that this norm can only be large if f correlates with e_F(Q(x)) for some polynomial Q : F^n -> F of degree at most d. The requirement deg(P) < |F| cannot be dropped entirely. Indeed, we show the above claim fails in characteristic 2 when d = 3 and deg(P)=4, showing that the quartic symmetric polynomial S_4 in F_2^n has large Gowers U^4-norm but does not correlate strongly with any cubic polynomial. This shows that the theory of Gowers norms in low characteristic is not as simple as previously supposed. This counterexample has also been discovered independently by Lovett, Meshulam, and Samorodnitsky. We conclude with sundry other applications of our main result, including a recurrence result and a certain type of nullstellensatz.

We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka the “short code” of Barak et al. [SIAM J. Comput., 44 (2015), pp. 1287--1324]) and the techniques proposed by Dinur and Guruswami [Israel J. Math., 209 (2015), pp. 611--649] to incorporate this code for inapproximability results. In particular, we prove quasi NP-hardness of the following problems on $n$-vertex hypergraphs: coloring a 2-colorable 8-uniform hypergraph with $2^{2^{\Omega(\sqrt{\log \log n})}}$ colors; coloring a 4-colorable 4-uniform hypergraph with $2^{2^{\Omega(\sqrt{\log \log n})}}$ colors; and coloring a 3-colorable 3-uniform hypergraph with $(\log n)^{\Omega(1/\log\log\log n)}$ colors. For the first two cases, the hardness results obtained are superpolynomial in what was previously known, and in the last case it is an exponential improvement. In fact, prior to this result, $(\log n)^{O(1)}$ colors was the strongest quantitative bound on the number of colors ruled out by inapproximability results for $O(1)$-colorable hypergraphs, and $(\log\log n)^{O(1)}$ for $O(1)$-colorable, 3-uniform hypergraphs.

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, 2014, pp. 119--127] and the $N^{\Omega(\log \log N)}$ lower bound in the independent work of [M. Kumar and S. Saraf, in Automata, Languages, and Programming, Part I, Springer, Berlin, 2014, pp. 751--762].

We make progress on some questions related to polynomial approximations of AC^0. It is known, from the works of Tarui (Theoret. Comput. Sci. 1993) and Beigel, Reingold, and Spielman (Proc. 6th CCC 1991), that any AC^0 circuit of size s and depth d has an epsilon-error probabilistic polynomial over the reals of degree (log (s/epsilon))^{O(d)}. We improve this upper bound to (log s)^{O(d)}* log(1/epsilon), which is much better for small values of epsilon. We give an application of this result by using it to resolve a question posed by Tal (ECCC 2014): we show that (log s)^{O(d)}* log(1/epsilon)-wise independence fools AC^0, improving on Tal's strengthening of Braverman's theorem (J. ACM 2010) that (log (s/epsilon))^{O(d)}-wise independence fools AC^0. Up to the constant implicit in the O(d), our result is tight. As far as we know, this is the first PRG construction for AC^0 that achieves optimal dependence on the error epsilon. We also prove lower bounds on the best polynomial approximations to AC^0. We show that any polynomial approximating the OR function on n bits to a small constant error must have degree at least ~Omega(sqrt{log n}). This result improves exponentially on a recent lower bound demonstrated by Meka, Nguyen, and Vu (arXiv 2015).

We show average-case lower bounds for explicit Boolean functions against bounded-depth threshold circuits with a superlinear number of wires. We show that for each integer d > 1, there is epsilon_d > 0 such that Parity has correlation at most 1/n^{Omega(1)} with depth-d threshold circuits which have at most n^{1+epsilon_d} wires, and the Generalized Andreev Function has correlation at most 1/2^{n^{Omega(1)}} with depth-d threshold circuits which have at most n^{1+epsilon_d} wires. Previously, only worst-case lower bounds in this setting were known [Impagliazzo/Paturi/Saks, SIAM J. Comp., 1997]. We use our ideas to make progress on several related questions. We give satisfiability algorithms beating brute force search for depth-$d$ threshold circuits with a superlinear number of wires. These are the first such algorithms for depth greater than 2. We also show that Parity cannot be computed by polynomial-size AC^0 circuits with n^{o(1)} general threshold gates. Previously no lower bound for Parity in this setting could handle more than log(n) gates. This result also implies subexponential-time learning algorithms for AC^0 with n^{o(1)} threshold gates under the uniform distribution. In addition, we give almost optimal bounds for the number of gates in a depth-d threshold circuit computing Parity on average, and show average-case lower bounds for threshold formulas ofany depth. Our techniques include adaptive random restrictions, anti-concentration and the structural theory of linear threshold functions, and bounded-read Chernoff bounds.

We consider the following multiplication-based tests to check if a given function f: F^n_q -> F_q is the evaluation of a degree-d polynomial over F_q for q prime. Test_{e,k}: Pick P_1,...,P_k independent random degree-e polynomials and accept iff the function f P_1 ... P_k is the evaluation of a degree-(d + ek) polynomial. We prove the robust soundness of the above tests for large values of e, answering a question of Dinur and Guruswami (FOCS 2013). Previous soundness analyses of these tests were known only for the case when either e = 1 or k = 1. Even for the case k = 1 and e > 1, earlier soundness analyses were not robust. We also analyze a derandomized version of this test, where (for example) the polynomials P_1 ,... , P_k can be the same random polynomial P. This generalizes a result of Guruswami et al. (STOC 2014). One of the key ingredients that go into the proof of this robust soundness is an extension of the standard Schwartz-Zippel lemma over general finite fields F_q, which may be of independent interest.

In this paper, we address the question of whether the recent derandomization results obtained by the use of the low-degree long code can be extended to other product settings. We consider two settings: (1) the graph product results of Alon, Dinur, Friedgut and Sudakov [GAFA, 2004] and (2) the "majority is stablest" type of result obtained by Dinur, Mossel and Regev [SICOMP, 2009] and Dinur and Shinkar [In Proc. APPROX, 2010] while studying the hardness of approximate graph coloring. In our first result, we show that there exists a considerably smaller subgraph of $K_3^{\otimes R}$ which exhibits the following property (shown for $K_3^{\otimes R}$ by Alon et al.): independent sets close in size to the maximum independent set are well approximated by dictators. The "majority is stablest" type of result of Dinur et al. and Dinur and Shinkar shows that if there exist two sets of vertices $A$ and $B$ in $K_3^{\otimes R}$ with very few edges with one endpoint in $A$ and another in $B$, then it must be the case that the two sets $A$ and $B$ share a single influential coordinate. In our second result, we show that a similar "majority is stablest" statement holds good for a considerably smaller subgraph of $K_3^{\otimes R}$. Furthermore using this result, we give a more efficient reduction from Unique Games to the graph coloring problem, leading to improved hardness of approximation results for coloring.

We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth-4 arithmetic formula computing the product of $d$ generic matrices of size $n \times n$, $\mathrm{IMM}_{n,d}$, has size $n^{\Omega(\sqrt{d})}$ as long as $d = n^{O(1)}$. This improves the result of Nisan and Wigderson [Comput. Complexity, 6 (1997), pp. 217--234] for depth-4 set-multilinear formulas. We also study $\Sigma\Pi^{[O(d/t)]}\Sigma\Pi^{[t]}$ formulas, which are depth-4 formulas with the stated bounds on the fan-ins of the $\Pi$ gates. A recent depth reduction result of Tavenas [Lecture Notes in Comput. Sci. 8087, 2013, pp. 813--824] shows that any $n$-variate degree $d = n^{O(1)}$ polynomial computable by a circuit of size $\mathop{\mathrm{poly}}(n)$ can also be computed by a depth-4 $\Sigma\Pi^{[O(d/t)]}\Sigma\Pi^{[t]}$ formula of top fan-in $n^{O(d/t)}$. We show that any such formula computing $\mathrm{IMM}_{n,d}$ has top fan-in $n^{\Omega({d/t})}$, proving the optimality of Tavenas' result. This also strengthens a result of Kayal, Saha, and Saptharishi [Proceedings of STOC, 2014, pp. 146--153], which gives a similar lower bound for an explicit polynomial in VNP.

We show here a 2Ω(√d ⋅ log N) size lower bound for homogeneous depth four arithmetic formulas. That is, we give an explicit family of polynomials of degree d on N variables (with N = d3 in our case) with 0, 1-coefficients such that for any representation of a polynomial f in this family of the form f = Σi ∏j Qij, where the Qij'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 ∑i, j (Number of monomials of Qij)) ≥2Ω(√d ⋅log N). The above mentioned family, which we refer to as the Nisan-Wigderson design-based family of polynomials, is in the complexity class VNP. Our work builds on recent lower bound results [1], [2], [3], [4], [5] and yields an improved quantitative bound as compared to the quasi-polynomial lower bound from an earlier work of the same authors and the NΩ(log log N) lower bound in the independent work of [7].

We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth 4 arithmetic formula computing the product of d generic matrices of size n × n, IMMn,d, has size nΩ(√d) as long as d = nO(1). This improves the result of Nisan and Wigderson (Computational Complexity, 1997) for depth 4 set-multilinear formulas.

We prove improved inapproximability results for hypergraph coloring using the low-degree polynomial code (aka, the"short code" of Barak et. al. [FOCS 2012]) and the techniques proposed by Dinur and Guruswami [FOCS 2013] to incorporate this code for inapproximability results.

We show that any depth-4 homogeneous arithmetic formula computing the Iterated Matrix Multiplication polynomial IMMn,d -- the (1, 1)-th entry of the product of d generic n × n matrices -- has size nΩ(log n), if d = Ω (log2 n). More-over, any depth-4 homogeneous formula computing the determinant polynomial Detn -- the determinant of a generic n × n matrix -- has size nΩ(log n).

Block sensitivity (bs(f)), certificate complexity (C(f)) and fractional certificate complexity (C*(f)) are three fundamental combinatorial measures of complexity of a boolean function f. It has long been known that bs(f) ≤ C*f ≤ C(f) =O(bs(f)2). We provide an infinite family of examples for which C(f) grows quadratic ally in C*(f) (and also bs(f)) giving optimal separations between these measures. Previously the biggest separation known was C(f)=C*(f)log4.55. We also give a family of examples for which C*(f)=Ω(bs(f)3/2). These examples are obtained by composing boolean functions in various ways. Here the composition f ο g of f with g is obtained by substituting for each variable of f a copy of g on disjoint sets of variables. To construct and analyse these examples we systematically investigate the behaviour under function composition of these measures and also the sensitivity measure s(f). The measures s(f), C(f) and C*(f) behave nicely under composition: they are sub multiplicative (where measure m is sub multiplicative if m(f ο g) ≤ m(f)m(g)) with equality holding under some fairly general conditions. The measure bs(f) is qualitatively different: it is not sub multiplicative. This qualitative difference was not noticed in the previous literature and we correct some errors that appeared in previous papers. We define the composition limit of a measure m at function f, mlim(f) to be the limit as k grows of m(f(k))1/k, where f(k)is the iterated composition of f with itself k-times. For any function f we show that bslim(f) = (C*)lim(f) and characterize slim(f), (C*)lim(f), and Clim(f) in terms of the largest eigenvalue of a certain set of 2 × 2 matrices associated with f.

A polynomial P in F[X_1,...,X_n] is said to epsilon-approximate a boolean function F:{0,1}^n -> {0,1} under distribution D over {0,1}^n if for a random x chosen according to distribution D, the probability that P(x) is not equal to F(x) is at most epsilon. Smolensky (1987) showed that for any constant distinct primes p and q, any polynomial P in F_p[x_1,...,x_n] that (1/2q - Omega(1))-approximates the boolean function MOD_q:{0,1}^n->{0,1} -- which accepts its input iff the number of ones is non-zero modulo q -- under the uniform distribution must have degree Omega(n^{1/2}). We consider the problem of finding an explicit function f:{0,1}^n->{0,1} that has no epsilon-approximating polynomial of degree less than n^{1/2 + Omega(1)} under *some distribution*, for some constant epsilon>0. We show a number of negative results in this direction: specifically, we show that many interesting classes of functions including symmetric functions and linear threshold functions do have approximating polynomials of degree O(n^{1/2+o(1)}) under every distribution. This demonstrates the power of this model of computation. The above results, in turn, provide further motivation for this lower bound question. Using the upper bounds obtained above, we show that finding such a function f would have applications to: lower bounds for AC^0 o F where F is the class of symmetric and threshold gates; stronger lower bounds for 1-round compression by ACC^0[p] circuits; improved correlation lower bounds against low degree polynomials; and (under further conditions) showing that the Inner Product (over F_2) function does not have small AC^0 o MOD_2 circuits.

We show how to approximate any function in AC0by decision trees of much smaller height than its number of variables. More precisely, we show that any function in n variables computable by an unbounded fan-in circuit of AND, OR, and NOT gates that has size S and depth d can be approximated by a decision tree of height n - βn to within error exp(-βn), where β = β(S, d) = 2-O(d log4/5S). Our proof is constructive and we use its constructivity to derive a deterministic algorithm for #AC0SAT with multiplicative factor savings over the naive 2nS algorithm of 2-Ω(βn), when applied to any n-input AC0circuit of size S and depth d. Indeed, in the same running time we can deterministically construct a decision tree of size at most 2n-βnthat exactly computes the function given by such a circuit. Recently, Impagliazzo, Matthews, and Paturi derived an algorithm for #AC0SAT with greater savings over the naive algorithm but their algorithm is only randomized rather than deterministic. The main technical result we prove to show the above is that for every family F of k-DNF formulas in n variables and every 1poly(k)|F|, one can construct a distribution on restrictions that each set at most n/C variables such that, except with probability at most2-n/(2O(k)Clog|T|), after application of the restriction, all formulas in F simultaneously reduce to logpoly(k)|F|-juntas where an s-junta is a function whose value depends on only s of its inputs. Previously, Ajtai showed simultaneous approximations for k-DNF formulas by juntas related to the one we show but with a dependence on exp(k) rather than poly(k), resulting in a weaker height-approximation tradeoff than ours.

We consider the problem of constructing pseudorandom generators for read-once circuits. We give an explicit construction of a pseudorandom generator for the class of read-once constant depth circuits with unbounded fan-in AND, OR, NOT and generalized modulo m gates, where m is an arbitrary fixed constant. The seed length of our generator is poly-logarithmic in the number of variables and the error.

In this paper, we introduce and develop the method of certifying polynomials for proving AC^0 circuit lower bounds. We use this method to show that Approximate Majority cannot be computed by AC^0(parity) circuits of size n^{1 + o(1)}. This implies a separation between the power of AC^0(parity) circuits of near-linear size and uniform AC^0(parity) (and even AC^0) circuits of polynomial size. This also implies a separation between randomized AC^0(parity) circuits of linear size and deterministic AC^0(parity) circuits of near-linear size. Our proof using certifying polynomials extends the deterministic restrictions technique of Chaudhuri and Radhakrishnan, who showed that Approximate Majority cannot be computed by AC^0 circuits of size n^{1+o(1)}. At the technical level, we show that for every ACP circuit C of near-linear size, there is a low degree variety V over F_2 such that the restriction of C to V is constant. We also prove other results exploring various aspects of the power of certifying polynomials. In the process, we show an essentially optimal lower bound of Omega\left(\log^{\Theta(d)} s \cdot \log \frac{1}{\epsilon} \right) on the degree of \epsilon-approximating polynomials for AC^0(parity) circuits of size s.

In this paper, we study the complexity of computing the determinant of a matrix over a non-commutative algebra. In particular, we ask the question, "over which algebras, is the determinant easier to compute than the permanent?" Towards resolving this question, we show the following hardness and easiness of noncommutative determinant computation. * [Hardness] Computing the determinant of an n \times n matrix whose entries are themselves 2 \times 2 matrices over a field is as hard as computing the permanent over the field. This extends the recent result of Arvind and Srinivasan, who proved a similar result which however required the entries to be of linear dimension. * [Easiness] Determinant of an n \times n matrix whose entries are themselves d \times d upper triangular matrices can be computed in poly(n^d) time. Combining the above with the decomposition theorem of finite dimensional algebras (in particular exploiting the simple structure of 2 \times 2 matrix algebras), we can extend the above hardness and easiness statements to more general algebras as follows. Let A be a finite dimensional algebra over a finite field with radical R(A). * [Hardness] If the quotient A/R(A) is non-commutative, then computing the determinant over the algebra A is as hard as computing the permanent. * [Easiness] If the quotient A/R(A) is commutative and furthermore, R(A) has nilpotency index d (i.e., the smallest d such that R(A)d = 0), then there exists a poly(n^d)-time algorithm that computes determinants over the algebra A. In particular, for any constant dimensional algebra A over a finite field, since the nilpotency index of R(A) is at most a constant, we have the following dichotomy theorem: if A/R(A) is commutative, then efficient determinant computation is feasible and otherwise determinant is as hard as permanent.

Using $\varepsilon$-bias spaces over $\F_2$, we show that the Remote Point Problem (RPP), introduced by Alon et al \cite{APY09}, has an $\NC^2$ algorithm (achieving the same parameters as \cite{APY09}). We study a generalization of the Remote Point Problem to groups: we replace $\F_2^n$ by $\mcG^n$ for an arbitrary fixed group $\mcG$. When $\mcG$ is Abelian we give an $\NC^2$ algorithm for RPP, again using $\varepsilon$-bias spaces. For nonabelian $\mcG$, we give a deterministic polynomial-time algorithm for RPP. We also show the connection to construction of expanding generator sets for the group $\mcG^n$. All our algorithms for the RPP achieve essentially the same parameters as \cite{APY09}.

\begin{abstract}

Motivated by the Hadamard product of matrices we define the Hadamard product of multivariate polynomials and study its arithmetic circuit and branching program complexity. We also give applications and connections to polynomial identity testing. Our main results are the following. \begin{itemize} \item[$\bullet$] We show that noncommutative polynomial identity testing for algebraic branching programs over rationals is complete for the logspace counting class $\ceql$, and over fields of characteristic $p$ the problem is in $\ModpL/\Poly$. \item[$\bullet$] We show an exponential lower bound for expressing the Raz-Yehudayoff polynomial as the Hadamard product of two monotone multilinear polynomials. In contrast the Permanent can be expressed as the Hadamard product of two monotone multilinear formulas of quadratic size. \end{itemize}

Using ideas from automata theory we design a new efficient (deterministic) identity test for the noncommutative polynomial identity testing problem (first introduced and studied in [RS05, BW05]). More precisely, given as input a noncommutative circuit C{x1, ldrldrldr , xn} computing a polynomial in F{x1, ldrldrldr , xn} of degree d with at most t monomials, where the variables xiare noncommuting, we give a deterministic polynomial identity test that checks if C equiv 0 and runs in time polynomial in d, n, |C|, and t. The same methods works in a black-box setting: given a noncommuting black-box polynomial f isin F{x1, ldrldrldr , xn} of degree d with t monomials we can, in fact, reconstruct the entire polynomial f in time polynomial in n, d and t. Indeed, we apply this idea to the reconstruction of black-box noncommuting algebraic branching programs (the ABPs considered by Nisan in [N91] and Raz-Shpilka in [RS05]). Assuming that the black-box model allows us to query the ABP for the output at any given gate then we can reconstruct an (equivalent) ABP in deterministic polynomial time. Finally, we turn to commutative identity testing and explore the complexity of the problem when the coefficients of the input polynomial come from an arbitrary finite commutative ring with unity whose elements are uniformly encoded as strings and the ring operations are given by an oracle. We show that several algorithmic results for polynomial identity testing over fields also hold when the coefficients come from such finite rings.