We study sparse polynomials with bounded individual degree and the class of their factors. In particular we obtain the following algorithmic and structural results: 1) A deterministic polynomial-time algorithm for finding all the sparse divisors of a sparse polynomial with bounded individual degree. As part of this, we establish the first upper bound on the number of non-monomial irreducible factors of such polynomials. 2) A poly(n,s^{dlog 𝓁})-time algorithm for recovering 𝓁 irreducible s-sparse polynomials of bounded individual degree d from blackbox access to their product (which is not necessarily sparse). This partially resolves a question posed in [Pranjal Dutta et al., 2024]. In particular, when 𝓁 = O(1), the algorithm runs in polynomial time. 3) Deterministic algorithms for factoring a product of s-sparse polynomials of bounded individual degree d from blackbox access. Over fields of characteristic zero or sufficiently large, the algorithm runs in poly(n,s^{d³log n})-time; over arbitrary fields it runs in poly(n,{(d²)!},s^{d⁵log n})-time. This improves upon the algorithm of [Bhargava et al., 2020], which runs in poly(n,s^{d⁷log n})-time and applies only to a single sparse polynomial of bounded individual degree. In the case where the input is a single sparse polynomial, we give an algorithm that runs in poly(n,s^{d²log n})-time. 4) Given blackbox access to a product of (not necessarily sparse or irreducible) factors of sparse polynomials of bounded individual degree, we give a deterministic polynomial-time algorithm for finding all irreducible sparse multiquadratic factors of it (along with their multiplicities). This generalizes the algorithms of [Volkovich, 2015] and [Volkovich, 2017]. We also show how to decide whether such a product is a complete power (in case it is defined over a field of zero or large enough characteristic), extending the algorithm of [Bisht and Volkovich, 2025]. Our algorithms most naturally apply over fields of zero or sufficiently large characteristic. To handle arbitrary fields, we introduce the notion of primitive divisors for a class of polynomials, which may be of independent interest. This notion enables us to adapt ideas of [Bisht and Volkovich, 2025] and remove characteristic assumptions from most of our algorithms.

A depth-4 algebraic circuit with top fan-in k and bottom fan-in 2 is a circuit Φ of the form Φ = ∑_{i = 1}^k ∏_{j = 1}^{m_i} Q_{ij}, where the polynomials Q_{ij} ∈ 𝕂[x₁, …, x_n] have degree at most 2. The class of all such circuits is denoted by Σ^k Π Σ Π². We say that the circuit Φ is an identity if it formally computes the zero polynomial. An important parameter of Σ^k Π Σ Π² circuits Φ is their (linear) rank, which is defined as the vector space dimension of the polynomials {Q_{ij}}_{i ∈ [k], j ∈ [m_i]}. We prove that, when the base field 𝕂 is of characteristic zero, the rank of any (simple and minimal) Σ^k Π Σ Π² identity is upper bounded by a function which depends only on the top fan-in k. This result makes progress on [Beecken et al., 2013], being the first work to establish a bound on the rank of such identities that depends only on the top fan-in. Moreover, when combined with [Beecken et al., 2013], our main result yields the first deterministic, polynomial time PIT algorithm for Σ^k Π Σ Π² circuits. One of the key components of our proof of the rank bounds is the derivation of an approximate Hansen-type result, which is interesting in its own right. This result can be seen as an algebraic and higher-dimensional analogue of the approximate Sylvester-Gallai result of [Ai et al., 2014], and a distinct approximate fractional Sylvester-Gallai result than the one from [Garg et al., 2023]. Additionally, we prove a robust version of it, in the spirit of the generalization of Hansen’s theorem by [Boaz Barak et al., 2013]. This paper is an extended abstract of the full version of the paper, which can be found at [Garg et al., 2026].

The partial derivative method is a central tool in algebraic complexity, underlying lower bounds for multilinear formulas, bounded depth circuits, and algebraic branching programs. A key feature of this measure is its subadditivity and submultiplicativity, which are usually used to upper bound the measure. However, proving lower bounds requires bounding the measure of explicit polynomials from below, and in some cases, a sharp estimate is required. For example, a frequently used fact is that the dimension of the space spanned by order k partial derivatives of a product of n linearly independent linear functions is binom(n,k). Beyond the linear case, however, not much is known about the behavior of the (general) partial derivative measure under multiplication. In particular, it has been conjectured that for algebraically independent polynomials g₁,… ,g_r ∈ ℂ[𝐱], the partial derivative complexity of the product ∏_{i=1}^r g_i(𝐱) grows exponentially with r (see [Chaugule et al., 2023]), but prior to this work such bounds were only known when the g_i’s are linear polynomials, or satisfy additional restrictions. In this paper, we show a lower bound of exp(Ω(r^{1/6})) for the measure of a product of r linearly independent quadratic polynomials. This is the first result to show such a lower bound on the partial derivative measure of a product of nonlinear polynomials, without any further restrictions. Interestingly, we only assume linear independence, which is weaker than algebraic independence. Our proof relies on algebraic-geometric and combinatorial techniques, combining the Jacobian approach of [Chaugule et al., 2023] together with the theory of wide algebras introduced in [Ananyan and Hochster, 2020; Oliveira and Sengupta, 2022; Garg et al., 2023]. To our knowledge, this is the first use of wide-algebra techniques for proving lower bounds on partial derivative complexity, and one of the first applications of these techniques outside the context of Sylvester-Gallai type problems.

Abstract We give reconstruction algorithms for subclasses of depth-3 arithmetic circuits. In particular, we obtain the first efficient algorithm for finding tensor rank and an optimal tensor decomposition as a sum of rank-one tensors, when given black-box access to a tensor of super-constant rank. Specifically, we obtain the following results: A randomized algorithm that reconstructs polynomials computed by multilinear $$\Sigma ^{[k]}\prod ^{[d]}\Sigma $$ Σ [ k ] ∏ [ d ] Σ circuits in time $$\textsf{poly}(n,d,c) \cdot k^{k^{k^{k^{O(k)}}}}$$ poly ( n , d , c ) · k k k k O ( k ) , A randomized algorithm that reconstructs polynomials computed by set-multilinear $$\Sigma ^{[k]}\prod ^{[d]}\Sigma $$ Σ [ k ] ∏ [ d ] Σ circuits in time $$\textsf{poly}(n,d,c) \cdot k^{k^{k^{k^{O(k)}}}}$$ poly ( n , d , c ) · k k k k O ( k ) , where $$c=\log q$$ c = log q if $$\mathbb {F}=\mathbb {F}_q$$ F = F q is a finite field, and c equals the maximum bit complexity of any coefficient of f if $$\mathbb {F}$$ F

Abstract Motivated by questions concerning the multilinear and homogeneous complexity of the elementary symmetric polynomials, we prove the following results: We first show that by making small modifications to the nonzero coefficients of the degree- K , N -variate elementary symmetric polynomial $$\sigma _{N,K}$$ σ N , K , one obtains a polynomial that can be computed by a monotone formula of size $$K^{O(\log K)} \cdot N$$ K O ( log K ) · N . As a corollary, we show that the result of (Raz 2013) concerning the homogenization of algebraic multilinear or monotone formulas is tight. Another corollary is that the monotone bounded rigidity of the inclusion matrix between K -subsets and $$N-K$$ N - K subsets of a universe of size N is small.

The purpose of this note is to correct an error made by Con et al. (2023), specifically in the proof of Theorem 9. Here we correct the proof but as a consequence we get a slightly weaker result. In Theorem9, we claimed that for integers k and n such that$k \lt n/9$, there exists an$[n,k]_{q}$RS code that can decode from$n-2k+1$insdel errors where$q = O\left ({{k^{5} \left ({{ \frac {en}{k-1} }}\right)^{4k-4}}}\right)$. Here we prove the following. Theorem 1: For integers n and$k \lt n/9$, there exists an$[n,k]_{q}$RS-code, where$q=O\left ({{k^{4} \cdot \left ({{\frac {4en}{4k-3}}}\right)^{4k-3}}}\right)$is a prime power, that can decode from$n - 2k + 1$adversarial insdel errors. Note that the exponent of n is$4k-3$whereas in Theorem 9 it is$4k-4$. For constant dimensional codes, the field size is of order$O(n^{4k-3})$, and in particular, for$k=2$the field size is of order$O(n^{5})$.

Tensor parameters that are amortized or regularized over large tensor powers, often called "asymptotic" tensor parameters, play a central role in several areas including algebraic complexity theory (constructing fast matrix multiplication algorithms), quantum information (entanglement cost and distillable entanglement), and additive combinatorics (bounds on cap sets, sunflower-free sets, etc.). Examples are the asymptotic tensor rank, asymptotic slice rank and asymptotic subrank. Recent works (Costa-Dalai, Blatter-Draisma-Rupniewski, Christandl-Gesmundo-Zuiddam) have investigated notions of discreteness (no accumulation points) or "gaps" in the values of such tensor parameters. We prove a general discreteness theorem for asymptotic tensor parameters of order-three tensors and use this to prove that (1) over any finite field (and in fact any finite set of coefficients in any field), the asymptotic subrank and the asymptotic slice rank have no accumulation points, and (2) over the complex numbers, the asymptotic slice rank has no accumulation points. Central to our approach are two new general lower bounds on the asymptotic subrank of tensors, which measures how much a tensor can be diagonalized. The first lower bound says that the asymptotic subrank of any concise three-tensor is at least the cube-root of the smallest dimension. The second lower bound says that any concise three-tensor that is "narrow enough" (has one dimension much smaller than the other two) has maximal asymptotic subrank. Our proofs rely on new lower bounds on the maximum rank in matrix subspaces that are obtained by slicing a three-tensor in the three different directions. We prove that for any concise tensor, the product of any two such maximum ranks must be large, and as a consequence there are always two distinct directions with large max-rank.

We prove that for monic polynomials <?TeX $f, g \in \mathbb {C}[x]$?> Math 1 such that g divides f, the ℓ2-norm of the quotient f/g is bounded by <?TeX $\left\Vert {f} \right\Vert _1 \cdot \tilde{O}(\left\Vert {g} \right\Vert _0^3\deg ^2{f})^{\left\Vert {g} \right\Vert _0 - 1}$?> Math 2 , improving upon the previously known exponential (in <?TeX $\deg (f)$?> Math 3 ) bounds for general polynomials. This result implies that the trivial long division algorithm runs in quasi-linear time relative to the input size and number of terms of the quotient, thus solving a long-standing problem. We also bound the number of terms of f/g in some special cases. When <?TeX $f, g \in \mathbb {Z}[x]$?> Math 4 and g is a cyclotomic-free (i.e., it has no cyclotomic factors) trinomial, we prove that <?TeX $\left\Vert {f/g} \right\Vert _0\le O(\left\Vert {f} \right\Vert _0 \text{size}\left(f \right)^2 \cdot \log ^6{\deg {g}})$?> Math 5 . When g is a binomial with g(± 1) ≠ 0, we prove that the sparsity is at most O(‖f‖0(log ‖f‖0 + log ‖f‖∞)). Both upper bounds are polynomial in the input-size. Leveraging these results, we provide a polynomial-time algorithm for deciding whether a cyclotomic-free trinomial divides a sparse polynomial over the integers.

Constructing Reed–Solomon (RS) codes that can correct insertions and deletions (insdel errors) has been considered in numerous recent works. Our focus in this paper is on the special case of two-dimensional RS-codes that can correct fromn- 3 insdel errors, the maximal possible number of insdel errors a two-dimensional linear code can recover from. It is known (by settingk= 2 in the lower bound [10, Proposition 37]) that an [n, 2]qRS-code that can correct fromn-3 insdel errors satisfies thatq= Ω(n3). On the other hand, there are several known constructions of [n, 2]qRS-codes that can correct fromn-3 insdel errors, where the smallest field size isq=O(n4). In this short paper, we construct [n, 2]qReed–Solomon codes that can correctn-3 insdel errors withq=O(n3), thereby resolving the minimum field size needed for such codes.

In this work, we study the performance of Reed–Solomon codes against adversarial insertion-deletion (insdel) errors. We prove that over fields of size$n^{O(k)}$there are$[n,k]$Reed-Solomon codes that can decode from$n-2k+1$insdel errors and hence attain the half-Singleton bound. We also give a deterministic construction of such codes over much larger fields (of size$n^{k^{O(k)}}$). Nevertheless, for$k=O(\log n /\log \log n)$our construction runs in polynomial time. For the special case$k=2$, which received a lot of attention in the literature, we construct an$[n], [2]$Reed-Solomon code over a field of size$O(n^{4})$that can decode from$n-3$insdel errors. Earlier constructions required an exponential field size. Lastly, we prove that any such construction requires a field of size$\Omega (n^{3})$.

In this work we extend the robust version of the Sylvester-Gallai theorem, obtained by Barak, Dvir, Wigderson and Yehudayoff, and by Dvir, Saraf and Wigderson, to the case of quadratic polynomials. Specifically, we prove that if {𝒬} ⊂ ℂ[x₁.…,x_n] is a finite set, |{𝒬}| = m, of irreducible quadratic polynomials that satisfy the following condition There is δ > 0 such that for every Q ∈ {𝒬} there are at least δ m polynomials P ∈ {𝒬} such that whenever Q and P vanish then so does a third polynomial in {𝒬}⧵{Q,P}. then dim(span) = Poly(1/δ). The work of Barak et al. and Dvir et al. studied the case of linear polynomials and proved an upper bound of O(1/δ) on the dimension (in the first work an upper bound of O(1/δ²) was given, which was improved to O(1/δ) in the second work).

In this work, we study the performance of Reed-Solomon codes against adversarial insertion-deletion (insdel) errors.We prove that over fields of size nO(k)there are [n, k] Reed-Solomon codes that can decode from n – 2k + 1 insdel errors and hence attain the half-Singleton bound. We also give a deterministic construction of such codes over much larger fields (of size ${n^{{k^{O(k)}}}}$). Nevertheless, for k = O(log n/ log log n) our construction runs in polynomial time. For the special case k = 2, which received a lot of attention in the literature, we construct an [n, 2] Reed-Solomon code over a field of size O(n4) that can decode from n – 3 insdel errors. Earlier constructions required an exponential field size. Lastly, we prove that any such construction requires a field of size Ω(n3).

Abstract. The purpose of this note is to correct mistakes and inaccuracies in technical claims in [Y. Rabani and A. Shpilka, Explicit Construction of a Small 𝜖 -net for Linear Threshold Functions, SIAM J. Comput., 39 (2010), pp. 3501–3520]. These have no effect on the main results in the paper.

This work gives an explicit construction of a family of error correcting codes for the binary deletion channel and for the Poisson repeat channel. In the binary deletion channel with parameter$p$(${\mathrm {BDC}}_{p}$) every bit is deleted independently with probability$p$. A lower bound of$(1-p)/9$is known on the capacity of the${\mathrm {BDC}}_{p}$, yet no explicit construction is known to achieve this rate. We give an explicit family of codes of rate$(1-p)/16$, for every$p$. This improves upon the work of Guruswami and Li (2018) that gave a construction of rate$(1-p)/120$. The codes in our family have polynomial time encoding and decoding algorithms. Another channel considered in this work is the Poisson repeat channel with parameter$\lambda $(PRC$_{\lambda }$) in which every bit is replaced with a discrete Poisson number of copies of that bit, where the number of copies has mean$\lambda $. We show that our construction works for this channel as well. As far as we know, this is the first explicit construction of an error correcting code for PRC$_{\lambda }$.

In this work, we study linear error-correcting codes against adversarial insertion-deletion (insdel) errors, a topic that has recently gained a lot of attention. We construct linear codes over$\mathbb {F}_{q}$, for$q= {\mathrm {poly}}(1/\varepsilon)$, that can efficiently decode from a$\delta $fraction of insdel errors and have rate$(1-4\delta)/8-\varepsilon $. We also show that by allowing codes over$\mathbb {F}_{q^{2}}$that are linear over$\mathbb {F}_{q}$, we can improve the rate to$(1-\delta)/4-\varepsilon $while not sacrificing efficiency. Using this latter result, we construct fully linear codes over$\mathbb {F}_{2}$that can efficiently correct up to$\delta < 1/54$fraction of deletions and have rate$R = (1-54\cdot \delta)/1216$. Chenget al.(2021) constructed codes with (extremely small) rates bounded away from zero that can correct up to a$\delta < 1/400$fraction of insdel errors. They also posed the problem of constructing linear codes that get close to thehalf-Singleton bound[proved in Chenget al.(2021)] over small fields. Thus, our results significantly improve their construction and get much closer to the bound.

A fundamental result in statistical learning theory is the equivalence of PAC learnability of a class with the finiteness of its Vapnik-Chervonenkis dimension. However, this clean result applies only to binary classification problems. In search for a similar combinatorial characterization of learnability in a more general setting, we discovered a surprising independence of set theory for some basic general notion of learnability. Consider the following statistical estimation problem: given a family F of real valued random variables over some domain X and an i.i.d. sample drawn from an unknown distribution P over X, find f in F such that its expectation w.r.t. P is close to the supremum expectation over all members of F. This Expectation Maximization (EMX) problem captures many well studied learning problems. Surprisingly, we show that the EMX learnability of some simple classes depends on the cardinality of the continuum and is therefore independent of the set theory ZFC axioms. Our results imply that that there exist no "finitary" combinatorial parameter that characterizes EMX learnability in a way similar to the VC-dimension characterization of binary classification learnability.

In this work we resolve conjectures of Beecken, Mitmann and Saxena [BMS13] and Gupta [Gupta14], by proving an analog of a theorem of Edelstein and Kelly for quadratic polynomials. As immediate corollary we obtain the first deterministic polynomial time black-box algorithm for testing zeroness of Σ[3]ΠΣΠ[2] circuits.

Reed-Muller (RM) codes are among the oldest, simplest and perhaps most ubiquitous family of codes. They are used in many areas of coding theory in both electrical engineering and computer science. Yet, many of their important properties are still under investigation. This paper covers some of the recent developments regarding the weight enumerator and the capacity-achieving properties of RM codes, as well as some of the algorithmic developments. In particular, the paper discusses the recent connections established between RM codes, thresholds of Boolean functions, polarization theory, hypercontractivity, and the techniques of approximating low weight codewords using lower degree polynomials (when codewords are viewed as evaluation vectors of degree r polynomials in m variables). It then overviews some of the algorithms for decoding RM codes. It covers both algorithms with provable performance guarantees for every block length, as well as algorithms with state-of-the-art performances in practical regimes, which do not perform as well for large block length. Finally, the paper concludes with a few open problems.

In this work we prove a version of the Sylvester-Gallai theorem for quadratic polynomials that takes us one step closer to obtaining a deterministic polynomial time algorithm for testing zeroness of Σ^{[3]}ΠΣΠ^{[2]} circuits. Specifically, we prove that if a finite set of irreducible quadratic polynomials 𝒬 satisfy that for every two polynomials Q₁,Q₂ ∈ 𝒬 there is a subset 𝒦 ⊂ 𝒬, such that Q₁,Q₂ ∉ 𝒦 and whenever Q₁ and Q₂ vanish then ∏_{Q_i∈𝒦} Q_i vanishes, then the linear span of the polynomials in 𝒬 has dimension O(1). This extends the earlier result [Amir Shpilka, 2019] that showed a similar conclusion when |𝒦| = 1. An important technical step in our proof is a theorem classifying all the possible cases in which a product of quadratic polynomials can vanish when two other quadratic polynomials vanish. I.e., when the product is in the radical of the ideal generated by the two quadratics. This step extends a result from [Amir Shpilka, 2019] that studied the case when one quadratic polynomial is in the radical of two other quadratics.

Algebraic complexity is the field studying the intrinsic difficulty of algebraic problems in an algebraic model of computation, most notably arithmetic circuits. It is a very natural model of computation that attracted a large amount of research in the last few decades, partially due to its simplicity and elegance, but mostly because of its importance. Being a more structured model than Boolean circuits, one could hope that the fundamental problems of theoretical computer science, such as separating P from NP, deciding whether P = BPP and more, will be easier to solve for arithmetic circuits. In this talk I will give the basic definitions, explain the main questions and how they relate to their Boolean counterparts, and discuss what I view as promising approaches to tackling the most fundamental problems in the field.

In the binary deletion channel with parameter p (BDCp) every bit is deleted independently with probability p. [1] proved a lower bound of (1-p)/9 on the capacity of the BDCp, yet currently no explicit construction achieves this rate. In this work we give an explicit family of codes of rate (1 -p)/16, for every p. This improves upon the work of Guruswami and Li [2] that gave a construction of rate (1-p)/120. The codes in our family have polynomial time encoding and decoding algorithms.

This work proves new results on the ability of binary Reed-Muller codes to decode from random errors and erasures. Specifically, we prove that RM codes with m variables and degree γm, for some explicit constant γ achieve capacity for random erasures (i.e. for the binary erasure channel) and for random errors (for the binary symmetric channel). Earlier, it was known that RM codes achieve capacity for the binary symmetric channel for degrees r = o(m). For the binary erasure channel it was known that RM codes achieve capacity for degree . Thus, our results provide a new range of parameters for which RM achieve capacity for these two well studied channels. In addition, our results imply that for every ϵ > 0 (in fact we can get up to RM codes of degree r < (1/2 – ϵ)m can correct a fraction of 1 – o(1) random erasures with high probability. We also show that, information theoretically, such codes can handle a fraction of random errors with high probability. For example, given noisy evaluations of a degree 0.499m polynomial, it is possible to interpolate it even if a random 0. 499 fraction of the evaluations were corrupted, with high probability. While the o(1) terms are not the correct ones to ensure capacity, these results show that RM codes of rates up to 1/poly(log n) (where n = 2m is the block length) are is some sense as good as capacity achieving codes. We obtain these results by proving improved bounds on the weight distribution of Reed-Muller codes of high degrees. Namely, given weight β ϵ (0, 1) we prove an upper bound on the number of codewords of relative weight at most β. We obtain new results in two different settings: for weights β < 1/2 and for weights that are close to 1/2. Our results for weights close to 1/2 also answer an open problem posed by Beame et al. [10].

We prove Sylvester-Gallai type theorems for quadratic polynomials. Specifically, we prove that if a finite collection Q, of irreducible polynomials of degree at most 2, satisfy that for every two polynomials Q1,Q2∈ Q there is a third polynomial Q3∈Q so that whenever Q1 and Q2 vanish then also Q3 vanishes, then the linear span of the polynomials in Q has dimension O(1). We also prove a colored version of the theorem: If three finite sets of quadratic polynomials satisfy that for every two polynomials from distinct sets there is a polynomial in the third set satisfying the same vanishing condition then all polynomials are contained in an O(1)-dimensional space.

In this paper we study the complexity of constructing a hitting set for VP, the class of polynomials that can be infinitesimally approximated by polynomials that are computed by polynomial sized algebraic circuits, over the real or complex numbers. Specifically, we show that there is a PSPACE algorithm that given n,s,r in unary outputs a set of rational n-tuples of size poly(n,s,r), with poly(n,s,r) bit complexity, that hits all n-variate polynomials of degree r that are the limit of size s algebraic circuits. Previously it was known that a random set of this size is a hitting set, but a construction that is certified to work was only known in EXPSPACE (or EXPH assuming the generalized Riemann hypothesis). As a corollary we get that a host of other algebraic problems such as Noether Normalization Lemma, can also be solved in PSPACE deterministically, where earlier only randomized algorithms and EXPSPACE algorithms (or EXPH assuming the generalized Riemann hypothesis) were known.

We formalize a framework of algebraically natural lower bounds for algebraic circuits. Just as with the natural proofs notion of Razborov and Rudich for boolean circuit lower bounds, our notion of algebraically natural lower bounds captures nearly all lower bound techniques known. However, unlike the boolean setting, there has been no concrete evidence demonstrating that this is a barrier to obtaining super-polynomial lower bounds for general algebraic circuits, as there is little understanding whether algebraic circuits are expressive enough to support "cryptography" secure against algebraic circuits.

Reed-Muller (RM) codes encode an m-variate polynomial of degree at most r by evaluating it on all points in {0,1}m. We denote this code by RM(r,m). The minimum distance of RM(r,m) is 2m-rand so it cannot correct more than half that number of errors in the worst case. For random errors one may hope for a better result. In this paper we give an efficient algorithm (in the block length n=2m) for decoding random errors in RM codes far beyond the minimum distance. Specifically, for low-rate codes (of degree r=o(√m)), we can correct a random set of (1/2-o(1))n errors with high probability. For high rate codes (of degree m-r for r=o(√m/log m)), we can correct roughly mr/2errors. More generally, for any integer r, our algorithm can correct any error pattern in RM(m-(2r+2),m), for which the same erasure pattern can be corrected in RM(m-(r+1),m). The results above are obtained by applying recent results of Abbe, Shpilka, and Wigderson (STOC, 2015) and Kudekar et al. (STOC, 2016) regarding the ability of RM codes to correct random erasures. The algorithm is based on solving a carefully defined set of linear equations and thus it is significantly different than other algorithms for decoding RM codes that are based on the recursive structure of the code. It can be seen as a more explicit proof of a result of Abbe et al. that shows a reduction from correcting erasures to correcting errors, and it also bares some similarities with the error-locating pair method of Pellikaan, Duursma, and Kötter that generalizes the Berlekamp-Welch algorithm for decoding Reed-Solomon codes.

Read-k oblivious algebraic branching programs are a natural generalization of the well-studied model of read-once oblivious algebraic branching program (ROABPs). In this work, we give an exponential lower bound of exp(n/k^{O(k)}) on the width of any read-k oblivious ABP computing some explicit multilinear polynomial f that is computed by a polynomial size depth-3 circuit. We also study the polynomial identity testing (PIT) problem for this model and obtain a white-box subexponential-time PIT algorithm. The algorithm runs in time 2^{~O(n^{1-1/2^{k-1}})} and needs white box access only to know the order in which the variables appear in the ABP.

We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the boolean setting for subsystems of Extended Frege proofs, where proof-lines are circuits from restricted boolean circuit classes. Except one, all of the subsystems considered in this paper can simulate the well-studied Nullstellensatz proof system, and prior to this work there were no known lower bounds when measuring proof size by the algebraic complexity of the polynomials (except with respect to degree, or to sparsity). We give two general methods of converting certain algebraic lower bounds into proof complexity ones. Our methods require stronger notions of lower bounds, which lower bound a polynomial as well as an entire family of polynomials it defines. Our techniques are reminiscent of existing methods for converting boolean circuit lower bounds into related proof complexity results, such as feasible interpolation. We obtain the relevant types of lower bounds for a variety of classes (sparse polynomials, depth-3 powering formulas, read-once oblivious algebraic branching programs, and multilinear formulas), and infer the relevant proof complexity results. We complement our lower bounds by giving short refutations of the previously-studied subset-sum axiom using IPS subsystems, allowing us to conclude strict separations between some of these subsystems.

Reed-Muller codes encode an m-variate polynomial of degree r by evaluating it on all points in {0,1}m. We denote this code by RM(m,r). The minimal distance of RM(m,r) is 2m−r and so it cannot correct more than half that number of errors in the worst case. For random errors one may hope for a better result.

In this paper we give subexponential size hitting sets for bounded depth multilinear arithmetic formulas. Using the known relation between black-box PIT and lower bounds we obtain lower bounds for these models. For depth-3 multilinear formulas, of size exp(n^delta), we give a hitting set of size exp(~O(n^(2/3 + 2*delta/3))). This implies a lower bound of exp(~Omega(n^(1/2))) for depth-3 multilinear formulas, for some explicit polynomial. For depth-4 multilinear formulas, of size exp(n^delta), we give a hitting set of size exp(~O(n^(2/3 + 4*delta/3)). This implies a lower bound of exp(~Omega(n^(1/4))) for depth-4 multilinear formulas, for some explicit polynomial. A regular formula consists of alternating layers of +,* gates, where all gates at layer i have the same fan-in. We give a hitting set of size (roughly) exp(n^(1-delta)), for regular depth-d multilinear formulas of size exp(n^delta), where delta = O(1/sqrt(5)^d)). This result implies a lower bound of roughly exp(~Omega(n^(1/sqrt(5)^d))) for such formulas. We note that better lower bounds are known for these models, but also that none of these bounds was achieved via construction of a hitting set. Moreover, no lower bound that implies such PIT results, even in the white-box model, is currently known. Our results are combinatorial in nature and rely on reducing the underlying formula, first to a depth-4 formula, and then to a read-once algebraic branching program (from depth-3 formulas we go straight to read-once algebraic branching programs).

In this work we study the quantitative relation between VC-dimension and two other basic parameters related to learning and teaching. Namely, the quality of sample compression schemes and of teaching sets for classes of low VC-dimension. Let C be a binary concept class of size m and VC-dimension d. Prior to this work, the best known upper bounds for both parameters were log(m), while the best lower bounds are linear in d. We present significantly better upper bounds on both as follows. We construct sample compression schemes of size exp(d) for C. This resolves a question of Littlest one and Warmuth (1986). Roughly speaking, we show that given an arbitrary set of labeled examples from an unknown concept in C, one can retain only a subset of exp(d) of them, in a way that allows to recover the labels of all other examples in the set, using additional exp(d) information bits. We further show that there always exists a concept c in C with a teaching set (i.e. A list of c-labeled examples uniquely identifying c in C) of size exp(d) log log(m). This problem was studied by Kuhlmann (1999). Our construction also implies that the recursive teaching (RT) dimension of C is at most exp(d) log log(m) as well. The RT-dimension was suggested by Zilles et al. And Doliwa et al. (2010). The same notion (under the name partial-ID width) was independently studied by Wigderson and Yehuday off (2013). An upper bound on this parameter that depends only on d is known just for the very simple case d=1, and is open even for d=2. We also make small progress towards this seemingly modest goal.

This paper studies the parameters for which binary Reed-Muller (RM) codes can be decoded successfully on the BEC and BSC, and in particular when can they achieve capacity for these two classical channels. Necessarily, the paper also studies properties of evaluations of multi-variate GF(2) polynomials on random sets of inputs. For erasures, we prove that RM codes achieve capacity both for very high rate and very low rate regimes. For errors, we prove that RM codes achieve capacity for very low rate regimes, and for very high rates, we show that they can uniquely decode at about square root of the number of errors at capacity.

An arithmetic read-once formula (ROF for short) is a formula (a circuit whose underlying graph is a tree) in which the operations are $${\left\{+, \times \right\}}$$ and such that every input variable labels at most one leaf. A preprocessed ROF (PROF for short) is a ROF in which we are allowed to replace each variable x i with a univariate polynomial T i (x i ). In this paper, we study the problems of designing deterministic identity testing algorithms for models related to preprocessed ROFs. Our main result gives PIT algorithms for the sum of k preprocessed ROFs, of individual degrees at most d (i.e., each T i (x i ) is of degree at most d), that run in time $${(nd)^{\mathcal{O}(k)}}$$ in the white-box setting and in time $${(nd)^{\mathcal{O}(k + \log n)}}$$ in the black-box setting. We also obtain better algorithms when the formulas have a small depth that lead to an improvement in the best PIT algorithm for multilinear depth-3 $${\Sigma\Pi\Sigma(k)}$$ circuits. Our main technique is to prove a hardness of representation result, namely a theorem showing a relatively mild lower bound on the sum of k PROFs. We then use this lower bound in order to design our PIT algorithm.

This paper studies the parameters for which binary Reed-Muller (RM) codes can be decoded successfully on the binary erasure channel and binary symmetry channel, and, in particular, when can they achieve capacity for these two classical channels. Necessarily, this paper also studies the properties of evaluations of multivariate GF(2) polynomials on the random sets of inputs. For erasures, we prove that RM codes achieve capacity both for very high rate and very low rate regimes. For errors, we prove that RM codes achieve capacity for very low rate regimes, and for very high rates, we show that they can uniquely decode at about the square root of the number of errors at capacity. The proofs of these four results are based on different techniques, which we find interesting in their own right. In particular, we study the following questions about E(m, r), the matrix whose rows are the truth tables of all the monomials of degree ≤ r in m variables. What is the most (resp. least) number of random columns in E(m, r) that define a submatrix having full column rank (resp. full row rank) with high probability? We obtain tight bounds for very small (resp. very large) degrees r, which we use to show that RM codes achieve capacity for erasures in these regimes. Our decoding from random errors follows from the following novel reduction. For every linear code C of sufficiently high rate, we construct a new code C' obtained by tensorizing C, such that for every subset S of coordinates, if C can recover from erasures in S, then C' can recover from errors in S. Specializing this to the RM codes and using our results for erasures imply our result on the unique decoding of the RM codes at high rate. Finally, two of our capacity achieving results require tight bounds on the weight distribution of RM codes. We obtain such bounds extending the recent bounds from constant degree to linear degree polynomials.

In this paper we show that the problem of deterministically factoring multivariate polynomials reduces to the problem of deterministic polynomial identity testing. Specifically, we show that given an arithmetic circuit (either explicitly or via black-box access) that computes a multivariate polynomial f, the task of computing arithmetic circuits for the factors of f can be solved deterministically, given a deterministic algorithm for the polynomial identity testing problem (we require either a white-box or a black-box algorithm, depending on the representation of f). Together with the easy observation that deterministic factoring implies a deterministic algorithm for polynomial identity testing, this establishes an equivalence between these two central derandomization problems of arithmetic complexity. Previously, such an equivalence was known only for multilinear circuits [SV10].

We show that in the model of zero error communication complexity, direct sum fails for average communication complexity as well as for external information cost. Our example also refutes a version of a conjecture by Braverman et al. that in the zero error case amortized communication complexity equals external information cost.

In this paper we prove results regarding Boolean functions with small spectral norm (the spectral norm of ƒ is ||ƒ||1 = ∑α|ƒ(α)|). Specifically, we prove the following results for functions ƒ :{0, 1}n → [0, 1}with ||ƒ||1 = A.

We give deterministic black-box polynomial identity testing algorithms for multilinear read-once oblivious algebraic branching programs (ROABPs), in nO(log2 n) time. Further, our algorithm is oblivious to the order of the variables. This is the first sub-exponential time algorithm for this model. Furthermore, our result has no known analogue in the model of read-once oblivious boolean branching programs with unknown order.

In this paper, we give an explicit construction of a family of capacity-achieving binary t-write WOM codes for any number of writes t, which have polynomial time encoding and decoding algorithms. The block length of our construction is N=(t/ε)O(t/(δε))when ε is the gap to capacity and encoding and decoding run in time N1+δ. This is the first deterministic construction achieving these parameters. Our techniques also apply to larger alphabets.

Write-once memory (WOM) is a storage medium with memory elements, called cells, which can take on q levels. Each cell is initially in level 0 and can only increase its level. A t-write WOM code is a coding scheme, which allows one to store t messages to the WOM such that on consecutive writes every cell's level does not decrease. The sum-rate of the WOM code, which is the ratio between the total amount of information written in the t writes and number of memory cells, is bounded by log(t + 1). Our main contribution in this paper is a construction of binary three-write WOM codes with sum-rate approaching 1.885 for sufficiently large number of cells, whereas the upper bound is 2. This improves upon a recent construction of sum-rate 1.809. A key ingredient in our construction is a recent capacity achieving construction of two-write WOM codes, which uses the so-called Wozencraft ensemble of linear codes. In our construction, we encode information in the first and second write in a way that leaves a large number (roughly half) of the cells nonprogrammed. This allows us to use the above two-write construction in order to invoke a third write to the memory. We also give specific constructions of nonbinary two-write WOM codes and multiple writes, which give better sum-rate than the currently best known ones. In the construction of these codes, we build upon previous nonbinary constructions and show how tools such symbols relabeling can help in achieving high sum-rates.

We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing algorithms (PIT) for algebraic branching programs (ABPs) that are read-once and oblivious. This class has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka), but prior to this work there was no known such black-box algorithm. The main result of this work gives the first quasi-polynomial sized hitting sets for size S circuits from this class, when the order of the variables is known. As our hitting set is of size exp(lg2S), this is analogous (in the terminology of boolean pseudorandom ness) to a seed-length of lg2S, which is the seed length of the pseudorandom generators of Nisan and Impagliazzo-Nisan-Wigderson for read-once oblivious boolean branching programs. Thus our work can be seen as an algebraic analogue of these foundational results in boolean pseudorandom ness. Our results are stronger for branching programs of bounded width, where we give a hitting set of size exp(lg2S/lglg S), corresponding to a seed length of lg2S/lglg S. This is in stark contrast to the known results for read-once oblivious boolean branching programs of bounded width, where no pseudorandom generator (or hitting set) with seed length o(lg2S) is known. Thus, while our work is in some sense an algebraic analogue of existing boolean results, the two regimes seem to have non-trivial differences. In follow up work, we strengthened a result of Mulmuley, and showed that derandomizing a particular case of the No ether Normalization Lemma is reducible to black-box PIT of read-once oblivious ABPs. Using the results of the present work, this gives a derandomization of No ether Normalization in that case, which Mulmuley conjectured would difficult due to its relations to problems in algebraic geometry. We also show that several other circuit classes can be black-box reduced to read-once oblivious ABPs, including set-multilinear ABPs (a generalization of depth-3 set-multilinear formulas), non-commutative ABPs (generalizing non-commutative formulas), and (semi-)diagonal depth-4 circuits (as introduced by Saxena). For set-multilinear ABPs and non-commutative ABPs, we give quasi-polynomial-time black-box PIT algorithms, where the latter case involves evaluations over the algebra of (D+1)x(D+1) matrices, where D is the depth of the ABP. For (semi-)diagonal depth-4 circuits, we obtain a black-box PIT algorithm (over any characteristic) whose run-time is quasi-polynomial in the runtime of Saxena's white-box algorithm, matching the concurrent work of Agrawal, Saha, and Saxena. Finally, by combining our results with the reconstruction algorithm of Klivans and Shpilka, we obtain deterministic reconstruction algorithms for the above circuit classes.

We present several variants of the sunflower conjecture of Erdős & Rado (J Lond Math Soc 35:85–90, 1960) and discuss the relations among them. We then show that two of these conjectures (if true) imply negative answers to the questions of Coppersmith & Winograd (J Symb Comput 9:251–280, 1990) and Cohn et al. (2005) regarding possible approaches for obtaining fast matrix-multiplication algorithms. Specifically, we show that the Erdős–Rado sunflower conjecture (if true) implies a negative answer to the “no three disjoint equivoluminous subsets” question of Coppersmith & Winograd (J Symb Comput 9:251–280, 1990); we also formulate a “multicolored” sunflower conjecture in $${\mathbb{Z}_3^n}$$ and show that (if true) it implies a negative answer to the “strong USP” conjecture of Cohn et al. (2005) (although it does not seem to impact a second conjecture in Cohn et al. (2005) or the viability of the general group-theoretic approach). A surprising consequence of our results is that the Coppersmith–Winograd conjecture actually implies the Cohn et al. conjecture. The multicolored sunflower conjecture in $${\mathbb{Z}_3^n}$$ is a strengthening of the well-known (ordinary) sunflower conjecture in $${\mathbb{Z}_3^n}$$ , and we show via our connection that a construction from Cohn et al. (2005) yields a lower bound of (2.51 . . .) n on the size of the largest multicolored 3-sunflower-free set, which beats the current best-known lower bound of (2.21 . . . ) n Edel (2004) on the size of the largest 3-sunflower-free set in $${\mathbb{Z}_3^n}$$ .

We give the first subexponential time deterministic polynomial identity testing algorithm for depth-4 multilinear circuits with a small top fan-in. More accurately, our algorithm works for depth-4 multilinear circuits with a plus gate at the top (also known as $\Sigma\Pi\Sigma\Pi$ circuits) and has a running time of $\exp(\mathrm{poly}(\log(n),\log(s),k))$ where $n$ is the number of variables, $s$ is the size of the circuit, and $k$ is the fan-in of the top gate. In particular, when the circuit is of polynomial (or quasi-polynomial) size, our algorithm runs in quasi-polynomial time. Prior to this work, sub-exponential time deterministic algorithms were known for depth-$3$ circuits with small top fan-in and for very restricted versions of depth-$4$ circuits. The main ingredient in our proof is a new structural theorem for multilinear $\Sigma\Pi\Sigma\Pi(k)$ circuits. Roughly, this theorem shows that any nonzero multilinear $\Sigma\Pi\Sigma\Pi(k)$ circuit contains an “embedded” nonzero multilinear $\Sigma\Pi\Sigma(k)$ circuit. Using ideas from previous works on identity testing of sums of read-once formulas and of depth-3 multilinear circuits, we are able to exploit this structure and obtain an identity testing algorithm for multilinear $\Sigma\Pi\Sigma\Pi(k)$ circuits.

In this paper, we give several new constructions of write-once-memory (WOM) codes. The novelty in our constructions is the use of the so-called Wozencraft ensemble of linear codes. Specifically, we obtain the following results. We give an explicit construction of a two-write WOM code that approaches capacity, over the binary alphabet. More formally, for every ϵ > 0, 0pn=(1/ϵ)O(1/pϵ), we give a construction of a two-write WOM code of lengthnand capacityH(p)+1-p-ϵ. Since the capacity of a two-write WOM code is maxp(H(p)+1-p), we get a code that is ϵ-close to capacity. Furthermore, encoding and decoding can be done in timeO(n2·poly (logn)) and timeO(n·poly (logn)), respectively, and in logarithmic space. In addition, we exhibit an explicit randomized encoding scheme of a two-write capacity-achieving WOM code of block length polynomial in 1/ϵ (again, ϵ is the gap to capacity), with a polynomial time encoding and decoding. We obtain a new encoding scheme for three-write WOM codes over the binary alphabet. Our scheme achieves rate 1.809-ϵ, when the block length is exp(1/ϵ). This gives a better rate than what could be achieved using previous techniques. We highlight a connection to linear seeded extractors for bit-fixing sources. In particular, we show that obtaining such an extractor with seed lengthO(logn) can lead to improved parameters for two-write WOM codes. We then give an application of existing constructions of extractors to the problem of designing encoding schemes for memory with defects.

We study the following problem raised by von zur Gathen and Roche [GR97]:

Write-once memory (WOM) is a storage medium with memory elements, called cells, which can take on q levels. Each cell is initially in level 0 and can only increase its level. A t-write WOM code is a coding scheme which allows one to store t messages to the WOM such that on consecutive writes every cell's level does not decrease. The sum-rate of the WOM code, which is the ratio between the total amount of information written in the t writes and the number of memory cells, is bounded by log2(t + 1). Our main contribution in this work is a construction of binary three-write WOM codes with sum-rate approaching 1.885 for sufficiently large number of cells, while the upper bound is 2. This improves upon a recent construction of sum-rate 1.809. We also give constructions of non-binary WOM codes which give better sum-rate than the currently best known ones.

We study the problem of obtaining efficient, deterministic, black-box polynomial identity testing algorithms for depth-3 set-multilinear circuits (over arbitrary fields). This class of circuits has an efficient, deterministic, white-box polynomial identity testing algorithm (due to Raz and Shpilka [36]), but has no known such black-box algorithm. We recast this problem as a question of finding a low-dimensional subspace H, spanned by rank 1 tensors, such that any non-zero tensor in the dual space ker(H) has high rank. We obtain explicit constructions of essentially optimal-size hitting sets for tensors of degree 2 (matrices), and obtain the first quasi-polynomial sized hitting sets for arbitrary tensors. We also show connections to the task of performing low-rank recovery of matrices, which is studied in the field of compressed sensing. Low-rank recovery asks (say, over R) to recover a matrix M from few measurements, under the promise that M is rank ≤ r. In this work, we restrict our attention to recovering matrices that are exactly rank ≤ r using deterministic, non-adaptive, linear measurements, that are free from noise. Over R, we provide a set (of size 4nr) of such measurements, from which M can be recovered in O(rn2+r3n) field operations, and the number of measurements is essentially optimal. Further, the measurements can be taken to be all rank-1 matrices, or all sparse matrices. To the best of our knowledge no explicit constructions with those properties were known prior to this work.

Locally testable codes, i.e., codes where membership in the code is testable with a constant number of queries, have played a central role in complexity theory. It is well known that a code must be a "low-density parity check'' (LDPC) code for it to be locally testable, but few LDPC codes are known to be locally testable, and even fewer classes of LDPC codes are known not to be locally testable. Indeed, most previous examples of codes that are not locally testable were also not LDPC. The only exception was in the work of Ben-Sasson et al. [SIAM J. Computing, 2005] who showed that random LDPC codes are not locally testable. Random codes lack "structure'' and in particular "symmetries'' motivating the possibility that "symmetric LDPC'' codes are locally testable, a question raised in the work of Alon et al. [IEEE Trans. Inf. Th., 2005]. If true such a result would capture many of the basic ingredients of known locally testable codes. In this work we rule out such a possibility by giving a highly symmetric ("2-transitive'') family of LDPC codes that are not testable with a constant number of queries. We do so by continuing the exploration of ``affine-invariant codes'' - codes where the coordinates of the words are associated with a finite field, and the code is invariant under affine transformations of the field. New to our study is the use of fields that have many subfields, and showing that such a setting allows sufficient richness to provide new obstacles to local testability, even in the presence of structure and symmetry.

We construct a small set of explicit linear transformations mapping $\mathbb{R}^n$ to $\mathbb{R}^t$, where $t=O(\log (\gamma^{-1}) \epsilon^{-2})$, such that the $L_2$ norm of any vector in $\mathbb{R}^n$ is distorted by at most $1\pm \epsilon$ in at least a fraction of $1 - \gamma$ of the transformations in the set. Albeit the tradeoff between the size of the set and the success probability is suboptimal compared with probabilistic arguments, we nevertheless are able to apply our construction to a number of problems. In particular, we use it to construct an $\epsilon$-sample (or pseudorandom generator) for linear threshold functions on $\mathbb{S}^{n-1}$ for $\epsilon = o(1)$. We also use it to construct an $\epsilon$-sample for spherical digons in $\mathbb{S}^{n-1}$ for $\epsilon = o(1)$. This construction leads to an efficient oblivious derandomization of the Goemans–Williamson Max-Cut algorithm and similar approximation algorithms (i.e., we construct a small set of hyperplanes such that for any instance we can choose one of them to generate a good solution). Our technique for constructing an $\epsilon$-sample for linear threshold functions on the sphere is considerably different than previous techniques that rely on k-wise independent sample spaces.

In this paper we give a new upper bound on the minimal degree of a nonzero Fourier coefficient in any non linear symmetric Boolean function. Specifically, we prove that for every non-linear and symmetric f : {0, 1}k→ {0,1} there exists a set Ø ≠ S ⊂ [k] such that |S| = O(Γ(k) + √k), and f̂(S) ≠ 0, where Γ(m) ≤ m0.525is the largest gap between consecutive prime numbers in {1,..., m}. As an application we obtain a new analysis of the PAC learning algorithm for symmetric juntas, under the uniform distribution, of Mossel et al. [JCSS, 2004]. Namely, we show that the running time of their algorithm is at most nO(k0.525)· poly(n · 2k,log · (1/δ)) where n is the number of variables, k is the size of the junta (i.e. number of relevant variables) and δ is the error probability. In particular, for k ≥ log(n)1/ (1-0-525)≈ log(n)2.1our analysis matches the lower bound 2k(up to polynomial factors). Our bound on the degree greatly improves the previous result of Kolountzakis et al. [Combinatorica, 2009] who proved that |S| = O(k/ log k).

A Locally Correctable Code (LCC) is an error correcting code that has a probabilistic self-correcting algorithm that, with high probability, can correct any coordinate of the codeword by looking at only a few other coordinates, even if a fraction δ of the coordinates are corrupted. LCCs are a stronger form of LDCs (Locally Decodable Codes) which have received a lot of attention recently due to their many applications and surprising constructions. In this work we show a separation between 2-query LDCs and LCCs over finite fields of prime order. Specifically, we prove a lower bound of the form p^{Ω(δd)} on the length of linear 2-query LCCs over $\F_p$, that encode messages of length d. Our bound improves over the known bound of $2^{Ω(δd)} \cite{GKST06, KdW04, DS07} which is tight for LDCs. Our proof makes use of tools from additive combinatorics which have played an important role in several recent results in theoretical computer science. Corollaries of our main theorem are new incidence geometry results over finite fields. The first is an improvement to the Sylvester-Gallai theorem over finite fields \cite{SS10} and the second is a new analog of Beck's theorem over finite fields.

We consider the problem of testing if a given function f : Fqn→Fqis close to a n-variate degree d polynomial over the finite field Fqof q elements. The natural, low-query, test for this property would be to pick the smallest dimension t = tq,d≈ d/q such that every function of degree greater than d reveals this aspect on some i-dimensional affine subspace of Fqnand to test that f when restricted to a random i-dimensional affine subspace is a polynomial of degree at most d on this subspace. Such a test makes only qtqueries, independent of n. Previous works, by Alon et al. [1], and Kaufman and Ron [7] and Jutla et al. [6], showed that this natural test rejected functions that were Ω(1)-far from degree d-polynomials with probability at least Ω,(q-t). (The initial work [1] considered only the case of q = 2, while the work [6] only considered the case of prime q. The results in [7] hold for all fields.) Thus to get a constant probability of detecting functions that are at constant distance from the space of degree d polynomials, the tests made q2tqueries. Kaufman and Ron also noted that when q is prime, then qtqueries are necessary. Thus these tests were off by at least a quadratic factor from known lower bounds. Bhattacharyya et al. [2] gave an optimal analysis of this test for the case of the binary field and showed that the natural test actually rejects functions that were Ω(1)-far from degree d- polynomials with probability Ω(1). In this work we extend this result for all fields showing that the natural test does indeed reject functions that are Ω(1)-far from degree d polynomials with Ω(1)-probability, where the constants depend only on q the field size. Thus our analysis thus shows that this test is optimal (matches known lower bounds) when q is prime. The main technical ingredient in our work is a tight analysis of the number of "hyperplanes" (affine subspaces of co-dimension 1) on which the restriction of a degree d polynomial has degree less than d. We show that the number of such hyperplanes is at most O(qtq-d) - which is tight to within constant factors.

We present a range of new results for testing properties of Boolean functions that are defined in terms of the Fourier spectrum. Broadly speaking, our results show that the property of a Boolean function having a concise Fourier representation is locally testable. We give the first efficient algorithms for testing whether a Boolean function has a sparse Fourier spectrum (small number of nonzero coefficients) and for testing whether the Fourier spectrum of a Boolean function is supported in a low-dimensional subspace of $\mathbb{F}_2^n$. In both cases we also prove lower bounds showing that any testing algorithm—even an adaptive one—must have query complexity within a polynomial factor of our algorithms, which are nonadaptive. Building on these results, we give an “implicit learning” algorithm that lets us test any subproperty of Fourier concision. We also present some applications of these results to exact learning and decoding. Our technical contributions include new structural results about sparse Boolean functions and new analysis of the pairwise independent hashing of Fourier coefficients from [V. Feldman, P. Gopalan, S. Khot, and A. Ponnuswami, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 563–576].

In this paper we give the first construction of a pseudorandom generator, with seed length O(log n), for CC0[p], the class of constant-depth circuits with unbounded fan-in MODpgates, for some prime p. More accurately, the seed length of our generator is O(log n) for any constant error ϵ > 0. In fact, we obtain our generator by fooling distributions generated by low degree polynomials, over Fp, when evaluated on the Boolean cube. This result significantly extends previous constructions that either required a long seed or that could only fool the distribution generated by linear functions over Fp, when evaluated on the Boolean cube. Enroute of constructing our PRG, we prove two structural results for low degree polynomials over finite fields that can be of independent interest. 1) Let f be an n-variate degree d polynomial over Fp. Then, for every ϵ > 0 there exists a subset S ⊂ [n], whose size depends only on d and ϵ, such that Σα∈Fpn:α≠0,αS=0|f̂(α)|2≤ ϵ. Namely, there is a constant size subset S such that the total weight of the nonzero Fourier coefficients that do not involve any variable from S is small. 2) Let f be an n-variate degree d polynomial over Fp. If the distribution of f when applied to uniform zero-one bits is ϵ-far (in statistical distance) from its distribution when applied to biased bits, then for every δ > 0, f can be approximated over zero-one bits, up to error δ, by a function of a small number (depending only on ϵ, δ and d) of lower degree polynomials.

In this paper we study the structure of polynomials of degree three and four that have high bias or high Gowers norm, over arbitrary prime fields. In particular we obtain the following results. 1. We give a canonical representation for degree three or four polynomials that have a significant bias (i.e. they are not equidistributed). This result generalizes the corresponding results from the theory of quadratic forms. This significantly improves previous results for such polynomials. 2. For the case of degree four polynomials with high Gowers norm we show that (a subspace of constant co-dimension of) Fn can be partitioned to subspaces of dimension Omega(n) such that on each of the subspaces the polynomial is equal to some degree three polynomial. It was previously shown that a quartic polynomial with a high Gowers norm is not necessarily correlated with any cubic polynomial. Our result shows that a slightly weaker statement does hold. The proof is based on finding a structure in the space of partial derivatives of the underlying polynomial.

We give the first sub-exponential time deterministic polynomial identity testing algorithm for depth-4 multilinear circuits with a small top fan-in. More accurately, our algorithm works for depth-4 circuits with a plus gate at the top (also known as ΣΠΣΠ circuits) and has a running time of exp(poly(log(n),log(s),k)) where n is the number of variables, s is the size of the circuit and k is the fan-in of the top gate. In particular, when the circuit is of polynomial (or quasi-polynomial) size, our algorithm runs in quasi-polynomial time. In [AV08], it was shown that derandomizing polynomial identity testing for general ΣΠΣΠ circuits implies a derandomization of polynomial identity testing in general arithmetic circuits. Prior to this work sub-exponential time deterministic algorithms were known for depth-$3$ circuits with small top fan-in and for very restricted versions of depth-4 circuits.

We give explicit constructions of $\epsilon$-nets for linear threshold functions on the binary cube and on the unit sphere. The size of the constructed nets is polynomial in the dimension n and in $\frac{1}{\epsilon}$. To the best of our knowledge no such constructions were previously known. Our results match, up to the exponent of the polynomial, the bounds that are achieved by probabilistic arguments. As a corollary we also construct subsets of the binary cube that have size polynomial in n and a covering radius of $\frac{n}{2}-c\sqrt{n\log n}$ for any constant c. This improves upon the well-known construction of dual BCH codes that guarantee only a covering radius of $\frac{n}{2}-c\sqrt{n}$.

Every Boolean function on n variables can be expressed as a unique multivariate polynomial modulo p for every prime p. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics. We establish the following general principle: functions with low degree modulo p must have high complexity in every other characteristic q. More precisely, we show the following results about Boolean functions f : {0,1}nrarr {0,1} which depend on all n variables, and distinct primes p, q: (1) If f has degree o(log n) modulo p, then it must have degree Omega(n1-o(1)) modulo q. Thus a Boolean function has degree o(log n) in only one characteristic. This result is essentially tight as there exist functions that have degree log n in every characteristic. (2) If f has degree d = o(log n) modulo p, it cannot be computed correctly on more than 1 - p-O(d)fraction of the hypercube by polynomials of degree n1/2-isinmodulo q. As a corollary of the above results it follows that if f has degree o(log n) modulo p, then it requires super-polynomial size A C0[q] circuits. This gives a lower bound for a broad and natural class of functions.

In this paper we give reconstruction algorithms for depth-3 arithmetic circuits with k multiplication gates (also known as SigmaPiSigma(k) circuits), where k=O(1). Namely, we give an algorithm that when given a black box holding a SigmaPiSigma(k) circuit C over a field F as input, makes queries to the black box (possibly over a polynomial sized extension field of F) and outputs a circuit C' computing the same polynomial as C. In particular we obtain the following results. (1) When C is a multilinear SigmaPiSigma(k) circuit (i.e. each of its multiplication gates computes a multilinear polynomial) then our algorithm runs in polynomial time (when k is a constant) and outputs a multilinear SigmaPiSigma(k) circuits computing the same polynomial. (2) In the general case, our algorithm runs in quasi-polynomial time and outputs a generalized depth-3 circuit with k multiplication gates. For example, the polynomials computed by generalized depth-3 circuits can be computed by quasi-polynomial sized depth-3 circuits. In fact, our algorithm works in the slightly more general case where the black box holds a generalized depth-3 circuits. Prior to this work there were reconstruction algorithms for several different models of bounded depth circuits: the well studied class of depth-2 arithmetic circuits (that compute sparse polynomials) and its close by model of depth-3 set-multilinear circuits. For the class of depth-3 circuits only the case of k = 2 (i.e. SigmaPiSigma(2) circuits) was known. Our proof technique combines ideas from previous works with some new ideas. Our most notable new ideas are: We prove the existence of a unique canonical representation of depth-3 circuits. This enables us to work with a specific representation in mind. Another technical contribution is an isolation lemma for depth-3 circuits that enables us to reconstruct a single multiplication gate of the circuit.

We give explicit constructions of epsilon nets for linear threshold functions on the binary cube and on the unit sphere. The size of the constructed nets is polynomial in the dimension n and in 1/ε. To the best of our knowledge no such constructions were previously known. Our results match, up to the exponent of the polynomial, the bounds that are achieved by probabilistic arguments. As a corollary we also construct subsets of the binary cube that have size polynomial in n and covering radius of n/2 - c√{n log n}, for any constant c. This improves upon the well known construction of dual BCH codes that only guarantee covering radius of n/2 - c√n.

In this paper we show that lower bounds for bounded depth arithmetic circuits imply derandomization of polynomial identity testing for bounded depth arithmetic circuits. More formally, if there exists an explicit polynomial f that cannot be computed by a depth d arithmetic circuit of small size, then there exists an efficient deterministic black-box algorithm to test whether a given depth $d-5$ circuit that computes a polynomial of relatively small individual degrees is identically zero or not. In particular, if we are guaranteed that the tested circuit computes a multilinear polynomial, then we can perform the identity test efficiently. To the best of our knowledge this is the first hardness-randomness tradeoff for bounded depth arithmetic circuits. The above results are obtained using the arithmetic Nisan–Wigderson generator of Kabanets and Impagliazzo together with a new theorem on bounded depth circuits, which is the main technical contribution of our work. This theorem deals with polynomial equations of the form $P(x_1,\dots,x_n,y)\equiv0$ and shows that if P has a circuit of depth d and size s and if the polynomial $f(x_1,\dots,x_n)$ satisfies $P(x_1,\dots,x_n,f)\equiv0$, then f has a circuit of depth $d+3$ and size $\mathrm{poly}(s,m^r)$, where m is the total degree of f and r is the degree of y in P. This circuit for f can be found probabilistically in time $\mathrm{poly}(s,m^r)$. In the other direction we observe that the methods of Kabanets and Impagliazzo can be used to show that derandomizing identity testing for bounded depth circuits implies lower bounds for the same class of circuits. More formally, if we can derandomize polynomial identity testing for bounded depth circuits, then NEXP does not have bounded depth arithmetic circuits. That is, either $\mathrm{NEXP}\not\subseteq P/\mathrm{poly}$ or the Permanent is not computable by polynomial size bounded depth arithmetic circuits.

We consider the problem of approximating the support size of a distribution from a small number of samples, when each element in the distribution appears with probability at least $\frac{1}{n}$. This problem is closely related to the problem of approximating the number of distinct elements in a sequence of length n. Charikar, Chaudhuri, Motwani, and Narasayya [in Proceedings of the Nineteenth ACM SIGMOD–SIGACT–SIGART Symposium on Principles of Database Systems, 2000, pp. 268–279] and Bar-Yossef, Kumar, and Sivakumar [in Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, ACM Press, New York, 2001, pp. 266–275] proved that multiplicative approximation for these problems within a factor $\alpha>1$ requires $\Theta(\frac{n}{\alpha^2})$ queries to the input sequence. Their lower bound applies only when the number of distinct elements (or the support size of a distribution) is very small. For both problems, we prove a nearly linear in n lower bound on the query complexity, applicable even when the number of distinct elements is large (up to linear in n) and even for approximation with additive error. At the heart of the lower bound is a construction of two positive integer random variables, $\mathsf{X}_1$ and $\mathsf{X}_2$, with very different expectations and the following condition on the first k moments: $\mathsf{E}[\mathsf{X}_1]/\mathsf{E}[\mathsf{X}_2] = \mathsf{E}[\mathsf{X}_1^2]/\mathsf{E}[\mathsf{X}_2^2] = \cdots = \mathsf{E}[\mathsf{X}_1^k]/\E[\mathsf{X}_2^k]$. It is related to a well-studied mathematical question, the truncated Hamburger problem, but differs in the requirement that our random variables have to be supported on integers. Our lower bound method is also applicable to other problems and, in particular, gives a new lower bound for the sample complexity of approximating the entropy of a distribution.

In this paper we consider the problem of constructing a small arithmetic circuit for a polynomial for which we have oracle access. Our focus is on n-variate polynomials, over a finite field $\mathbb{F}$, that have depth-3 arithmetic circuits (with an addition gate at the top) with two multiplication gates of degree at most d. We obtain the following results: 1. Multilinear case. When the circuit is multilinear (multiplication gates compute multilinear polynomials) we give an algorithm that outputs, with probability $1-o(1)$, all the depth-3 circuits with two multiplication gates computing the polynomial. The running time of the algorithm is $\operatorname{poly}(n,|\mathbb{F}|)$. 2. General case. When the circuit is not multilinear we give a quasi-polynomial (in $n,d,|\mathbb{F}|$) time algorithm that outputs, with probability $1-o(1)$, a succinct representation of the polynomial. In particular, if the depth-3 circuit for the polynomial is not of small depth-3 rank (namely, after removing the g.c.d. (greatest common divisor) of the two multiplication gates, the remaining linear functions span a not too small linear space), then we output the depth-3 circuit itself. In the case that the rank is small we output a depth-3 circuit with a quasi-polynomial number of multiplication gates. $\diamond$ Prior to our work there have been several interpolation algorithms for restricted models. However, all the techniques used there completely fail when dealing with depth-3 circuits with even just two multiplication gates. Our proof technique is new and relies on the factorization algorithm for multivariate black-box polynomials, on lower bounds on the length of linear locally decodable codes with two queries, and on a theorem regarding the structure of identically zero depth-3 circuits with four multiplication gates.

A noisy interpolating set (NIS) for degree d polynomials is a set S sube Fn, where F is a finite field, such that any degree d polynomial q isin F[x1,..., xn] can be efficiently interpolated from its values on S, even if an adversary corrupts a constant fraction of the values. In this paper we construct explicit NIS for every prime field Fpand any degree d. Our sets are of size O(nd) and have efficient interpolation algorithms that can recover qfrom a fraction exp(-O(d)) of errors. Our construction is based on a theorem which roughly states that ifS is a NIS for degree I polynomials then dldrS = {alpha1+ ... + alphad| alpha1isin S} is a NIS for degree d polynomials. Furthermore, given an efficient interpolation algorithm for S, we show how to use it in a black-box manner to build an efficient interpolation algorithm for d ldr S. As a corollary we get an explicit family of punctured Reed-Muller codes that is a family of good codes that have an efficient decoding algorithm from a constant fraction of errors. To the best of our knowledge no such construction was known previously.

In this paper we consider the problem of determining whether an unknown arithmetic circuit, for which we have oracle access, computes the identically zero polynomial. This problem is known as the black-box polynomial identity testing (PIT) problem. Our focus is on polynomials that can be written in the form f(xmacr) = Sigmai=1khi(xmacr) ldr gi(xmacr), where each hi is a polynomial that depends on at most p linear functions, and each giis a product of linear functions (when hi= 1, for each i, then we get the class of depth-3 circuits with k multiplication gates, also known as SigmaPiSigma(k) circuits, but the general case is much richer). When maxi(deg(hildrgi)) = d we say that f is computable by a SigmaPiSigma(k, d, p) circuit. We obtain the following results. 1. A deterministic black-box identity testing algorithm for SigmaPiSigma(k, d, p) circuits that runs in quasi-polynomial time (for p = polylog(n + d)). 2. A deterministic black-box identity testing algorithm for read-k SigmaPiSigma circuits (depth-3 circuits where each variable appears at most k times) that runs in time n2o(k2)This gives a polynomial time algorithm for k = 0(1). These are the first sub-exponential black-box PIT algorithms for circuits of depth higher than 2. Our results can also be stated in terms of test sets for the underlying circuit model. A test set is a set of points s.t. if two circuits get the same values on every point of the set then they compute the same polynomial. Thus, our first result gives an explicit test set, of quasi-polynomial size, for SigmaPiSigma(k, d, p) circuits (for p = polylog(n + d)). Our second result gives an explicit polynomial size test set for read-k depth-3 circuits. The proof technique involves a construction of a family of affine subspaces that have a rank-preserving property that is inspired by the construction of linear seeded extractors for affine sources of Gabizon andRaz [9], and a generalization of a theorem of [8] regarding the structure of identically zero depth-3 circuits with bounded top fan-in.

We construct an explicit polynomial $f(x_1,\dots,x_n)$, with coefficients in $\{0,1\}$, such that the size of any syntactically multilinear arithmetic circuit computing f is at least $\Omega(n^{4/3}/\log^2n)$. The lower bound holds over any field.

We consider the problem of approximating the support size of a distribution from a small number of samples, when each element in the distribution appears with probability at least 1/n. This problem is closely related to the problem of approximating the number of distinct elements in a sequence of length n. For both problems, we prove a nearly linear in n lower bound on the query complexity, applicable even for approximation with additive error. At the heart of the lower bound is a construction of two positive integer random variables. X1and X2, with very different expectations and the following condition on the first k moments: E[X1]/E[X2] = E[X12]/E[X22] = ... = E[X1k]/E[X2k]. Our lower bound method is also applicable to other problems. In particular, it gives new lower bounds for the sample complexity of (1) approximating the entropy of a distribution and (2) approximating how well a given string is compressed by the Lempel-Ziv scheme.

We construct an explicit polynomial f(x1,..., xn), with coefficients in {0, 1}, such that the size of any syntactically multilinear arithmetic circuit computing f is at least Omega{n4/3log2n} The lower bound holds over any field.

In this paper we consider the problem of constructing a small arithmetic circuit for a polynomial for which we have oracle access. Our focus is on n-variate polynomials, over a finite field F, that have depth-3 arithmetic circuits with two multiplication gates of degree d. We obtain the following results: 1. Multilinear case: When the circuit is multilinear (multiplication gates compute multilinear polynomials) we give an algorithm that outputs, with probability 1 − o(1), all the depth-3 circuits with two multiplication gates computing the same polynomial. The running time of the algorithm is poly(n, |F|). 2. General case: When the circuit is not multilinear we give a quasi-polynomial (in n, d, |F|) time algorithm that outputs, with probability 1 − o(1), a succinct representation of the polynomial. In particular, if the depth-3 circuit for the polynomial is not of small depth-3 rank (namely, after removing the g.c.d. of the two multiplication gates, the remaining linear functions span a not too small linear space) then we output the depth-3 circuit itself. In case that the rank is small we output a depth-3 circuit with a quasi-polynomial number of multiplication gates. Our proof technique is new and relies on the factorization algorithm for multivariate black-box polynomials, on lower bounds on the length of linear locally decodable codes with 2 queries, and on a theorem regarding the structure of identically zero depth-3 circuits with four multiplication gates.

In this work we study two, seemingly unrelated, notions. Locally decodable codes (LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial identity testing (PIT) is one of the fundamental problems of algebraic complexity: we are given a circuit computing a multivariate polynomial and we have to determine whether the polynomial is identically zero. We improve known results on LDCs and on polynomial identity testing and show a relation between the two notions. In particular we obtain the following results: (1) We show that if $E: \mathbb{F}^n \mapsto \mathbb{F}^m$ is a linear LDC with two queries, then $m = \exp(\Omega(n))$. Previously this was known only for fields of size $\ll 2^n$ [O. Goldreich et al., Comput. Complexity, 15 (2006), pp. 263–296]. (2) We show that from every depth 3 arithmetic circuit ($\Sigma\Pi\Sigma$ circuit), ${\cal C}$, with a bounded (constant) top fan‐in that computes the zero polynomial, one can construct an LDC. More formally, assume that ${\cal C}$ is minimal (no subset of the multiplication gates sums to zero) and simple (no linear function appears in all the multiplication gates). Denote by d the degree of the polynomial computed by ${\cal C}$ and by r the rank of the linear functions appearing in ${\cal C}$. Then we can construct a linear LDC with two queries that encodes messages of length $r/{\operatorname{polylog}(d)}$ by codewords of length $O(d)$. (3) We prove a structural theorem for $\Sigma\Pi\Sigma$ circuits, with a bounded top fan‐in, that compute the zero polynomial. In particular we show that if such a circuit is simple, minimal, and of polynomial size, then its rank, r, is only polylogarithmic in the number of variables (a priori it could have been linear). (4) We give new PIT algorithms for $\Sigma\Pi\Sigma$ circuits with a bounded top fan‐in: (a) a deterministic algorithm that runs in quasipolynomial time, and (b) a randomized algorithm that runs in polynomial time and uses only a polylogarithmic number of random bits. Moreover, when the circuit is multilinear, our deterministic algorithm runs in polynomial time. Previously deterministic subexponential time algorithms for PIT in bounded depth circuits were known only for depth 2 circuits (in the black box model) [D. Grigoriev, M. Karpinski, and M. F. Singer, SIAM J. Comput., 19 (1990), pp. 1059–1063; M. Ben‐Or and P. Tiwari, Proceedings of the 20th Annual ACM Symposium on Theory of Computing, ACM Press, New York, 1988, pp. 301–309; A. R. Klivans and D. Spielman, Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, ACM Press, New York, 2001, pp. 216–223]. In particular, for the special case of depth 3 circuits with three multiplication gates our result resolves an open question asked by Klivans and Spielman.

In this work we give two new constructions of epsi-biased generators. Our first construction answers an open question of Dodis and Smith (2005), and our second construction significantly extends a result of Mossel et al. (2003). In particular we obtain the following results: (1) We construct a family of asymptotically good binary codes such that the codes in our family are also epsi-biased sets for an exponentially small epsi. Our encoding and decoding algorithms run in polynomial time in the block length of the code. This answers an open question of Dodis and Smith (2005). (2) For every k = o(log n) we construct a degree k epsi-biased generator G:{0, 1}mrarr {0,1}n(namely, every output bit of the generator is a degree k polynomial in the input bits). For k constant we get that n = Omega(m/log(1/epsi))k, which is nearly optimal. Our result also separates degree k generators from generators in NCk0, showing that the stretch of the former can be much larger than the stretch of the latter. The problem of constructing degree k generators was introduced by Mossel et al. (2003) who gave a construction only for the case of degree 2 generators

The main result of this paper is a near‐optimal derandomization of the affine homomorphism test of Blum, Luby, and Rubinfeld [J. Comput. System Sci., 47 (1993), pp. 549–595]. We show that for any groups G and Γ, and any expanding generating set S of G, the natural deramdomized version of the BLR test in which we pick an element x randomly from G and y randomly from S and test whether $f(x)\cdot f(y)=f(x\cdot y)$, performs nearly as well (depending of course on the expansion) as the original test. Moreover, we show that the underlying homomorphism can be found by the natural local “belief propagation decoding.” We note that the original BLR test uses $2\log_2 |G|$ random bits, whereas the derandomized test uses only $(1+o(1))\log_2 |G|$ random bits. This factor of 2 savings in the randomness complexity translates to a near quadratic savings in the length of the tables in the related locally testable codes (and possibly probabilistically checkable proofs which may use them). Our result is a significant generalization of recent results that either refer to the special case of the groups $G=Z_p^m$ and $Γ =Z_p$ or are nonconstructive. We use simple combinatorial arguments and the transitivity of Cayley graphs (and this analysis gives optimal results up to constant factors). Previous techniques used the Fourier transform, a method which seems unextendable to general groups (and furthermore gives suboptimal bounds). Finally, we provide a polynomial time (in $|G|$) construction of a (somewhat) small ($|G|^{\epsilon}$) set of expanding generators for every group G, which yield efficient testers of randomness $(1+\epsilon) \log |G|$ for G. This result follows from a simple derandomization of a known probabilistic construction.

In this work we study two, seemingly unrelated, notions. Locally Decodable Codes (LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial Identity Testing (PIT) is one of the fundamental problems of algebraic complexity: we are given a circuit computing a multivariate polynomial and we have to determine whether the polynomial is identically zero. We improve known results on locally decodable codes and on polynomial identity testing and show a relation between the two notions. In particular we obtain the following results:

Cyclic linear codes of block length n over a finite field F/sub q/ are linear subspaces of F/sub q//sup n/ that are invariant under a cyclic shift of their coordinates. A family of codes is good if all the codes in the family have constant rate and constant normalized distance (distance divided by block length). It is a long-standing open problem whether there exists a good family of cyclic linear codes. A code C is r-testable if there exists a randomized algorithm which, given a word x/spl isin//sub q//sup n/, adaptively selects r positions, checks the entries of x in the selected positions, and makes a decision (accept or reject x) based on the positions selected and the numbers found, such that 1) if x/spl isin/C then x is surely accepted; ii) if dist(x,C) /spl ges/ /spl epsi/n then x is probably rejected. ("dist" refers to Hamming distance.) A family of codes is locally testable if all members of the family are r-testable for some constant r. This concept arose from holographic proofs/PCP's. Recently it was asked whether there exist good, locally testable families of codes. In this paper the intersection of the two questions stated is addressed. Theorem. There are no good, locally testable families of cyclic codes over any (fixed) finite field. In fact the result is stronger in that it replaces condition ii) of local testability by the condition ii') if dist (x,C) /spl ges/ /spl epsi/n then x has a positive chance of being rejected. The proof involves methods from Galois theory, cyclotomy, and diophantine approximation.

We give a deterministic polynomial time algorithm for polynomial identity testing in the following two cases: 1. Non commutative arithmetic formulas: the algorithm gets as an input an arithmetic formula in the non-commuting variables x/sub i/,...,x/sub n/ and determines whether or not the output of the formula is identically 0 (as a formal expression). 2. Pure arithmetic circuits: the algorithm gets as an input a pure arithmetic circuit (as defined by N. Nisan and A. Wigderson (1996)) in the variables x/sub i/,...,x/sub n/ and determines whether or not the output of the circuit is identically 0 (as a formal expression). We also give a deterministic polynomial time identity testing algorithm for non commutative algebraic branching programs as defined by N. Nisan (1991). One application is a deterministic polynomial time identity testing for multilinear arithmetic circuits of depth 3. Finally, we observe an exponential lower bound for the size of pure arithmetic circuits for the permanent and for the determinant. (Only lower bounds for the depth of pure circuits were previously known by N. Nisan and A. Wigderson (1996).

We study the power of quantum proofs, or more precisely, the power of quantum Merlin-Arthur (QMA) protocols, in two well studied models of quantum computation: the black box model and the communication complexity model. Our main results are obtained for the communication complexity model. For this model, we identify a complete promise problem for QMA protocols, the linear sub-spaces distance problem. The problem is of geometrical nature: each player gets a linear subspace of R/sup m/ and considers the sphere of unit vectors in that subspace. Their goal is to output 1 if the distance between the two spheres is very small (say, smaller than 0.1 /spl middot/ /spl radic/2) and 0 if the distance is very large (say, larger than 0.9 /spl middot/ /spl radic/2). We show that: 1. The QMA communication complexity of the problem is O(logm). 2. The (classical) MA communication complexity of the problem is /spl Omega/(m/sup /spl epsi//) (for some /spl epsi/ > 0). 3. The (standard) quantum communication complexity of the problem is /spl Omega/(/spl radic/m). In particular, this gives an exponential separation between QMA communication complexity and MA communication complexity. For the black box model we give several observations. First, we observe that the block sensitivity method, as well as the polynomial method for proving lower bounds for the number of queries, can both be extended to QMA protocols. We use these methods to obtain lower bounds for the QMA black box complexity of functions. In particular, we obtain a tight lower bound of /spl Omega/(N) for the QMA black box complexity of a random function, and a tight lower bound of /spl Omega/(/spl radic/N) for the QMA black box query complexity of NOR(X/sub 1/,..., X/sub n/). In particular, this shows that any attempt to give short quantum proofs for the class of languages Co - NP have to go beyond black box arguments. We also observe that for any Boolean function G(X/sub 1/,..., X/sub n/), if for both G and 7minus;G there are QMA black box protocols that make at most T queries to the black box, then there is a classical deterministic black box protocol for G that makes 0(T/sup 6/) queries to the black box. In particular, this shows that in the black box model QMA /spl cap/ Co - QMA = P. On the positive side, we observe that any (total or partial) Boolean function G(X/sub 1/,..., X/sub n/) has a QMA black box protocol with proofs of length N that makes only 0(/spl radic/N) queries to the black box. Finally, we observe a very simple proof for the exponential separation (for promise problems) between QMA black box complexity and (classical) MA black box complexity (first obtained by Watrous).

The main result of this paper is a near-optimal derandomization of the affine homomorphism test of Blum, Luby and Rubinfeld [11]. We show that for any groups G and Γ, and any expanding generating set S of G, the natural deramdomized version of the BLR test in which we pick an element x randomly from G and y randomly from S and test whether f(x) · f(y)=f(x · y), performs nearly as well (depending of course on the expansion) as the original test. Moreover we show that the underlying homomorphism can be found by the natural local "belief propagation decoding". We note that the original BLR test uses 2 log2 |G| random bits, whereas the derandomized test uses only (1+o(1)) log2 |G| random bits. This factor of 2 savings in the randomness complexity translates to a near quadratic savings in the length of the tables in the related locally testable codes (and possibly probabilistically checkable proofs which may use them). Our result is a significant generalization of the recent result of [12], who proved such a result only for the groups G=Zpm and Γ=Zp. It is also an explicit version of the nonconstructive result of [18]. We use a simple combinatorial arguments and the transitivity of Cayley graphs (and this analysis gives optimal results up to constant factors). Previous techniques used the Fourier transform, a method which seems unextendable to general groups (and furthermore gives suboptimal bounds). Finally, we provide a polynomial time (in |G|) construction of a (somewhat) small (|G|ε) set of expanding generators for every group G, which yield efficient testers of randomness (1+ε) log |G| for G. This follows a simple derandomization of the probabilistic construction of [5], who showed that almost all logarithmic-size sets are expanding. Our work motivates further study of similar derandomizations of other natural property testing procedures, especially those more relevant to the local testing of better codes and to PCPs.

Cyclic linear codes of block length n over a finite field F/sub q/ are the linear subspaces of F/sub q//sup n/ that are invariant under a cyclic shift of their coordinates. A family of codes is good if all the codes in the family have constant rate and constant normalized distance (distance divided by block length). It is a long-standing open problem whether there exists a good family of cyclic linear codes based on F.J. MacWilliams and N.J.A. Sloane (1977). A code C is r-testable if there exist a randomized algorithm which, given a word x /spl isin/ F/sub q//sup n/, adaptively selects r positions, checks the entries of x in the selected positions, and makes a decision (accept or reject x) based on the positions selected and the numbers found, such that (i) if x /spl isin/ C then x is surely accepted; (ii) if dist(x,C) /spl ges/ /spl epsi/n then x is probably rejected (dist refers to Hamming distance). A family of codes is locally testable if all members of the family are r-testable for some constant r. This concept arose from holographic proofs/PCPs. O. Goldreich and M. Sudan (2002) asked whether there exist good, locally testable families of codes. In this paper we address the intersection of the two questions stated.

M. Cryan and P.B. Miltersen (2001) recently considered the question of whether there can be a pseudorandom generator in NC/sup 0/, that is, a pseudorandom generator that maps n bits strings to m bits strings and such that every bit of the output depends on a constant number k of bits of the seed. They show that for k = 3, if m /spl ges/ 4n + 1, there is a distinguisher; in fact, they show that in this case it is possible to break the generator with a linear test, that is, there is a subset of bits of the output whose XOR has a noticeable bias. They leave the question open for k /spl ges/ 4. In fact they ask whether every NC/sup 0/ generator can be broken by a statistical test that simply XORs some bits of the input. Equivalently, is it the case that no NC/sup 0/ generator can sample an /spl epsiv/-biased space with negligible /spl epsiv/? We give a generator for k = 5 that maps n bits into cn bits, so that every bit of the output depends on 5 bits of the seed, and the XOR of every subset of the bits of the output has bias 2/sup -/spl Omega/(n/c4)/. For large values of k, we construct generators that map n bits to n/sup /spl Omega/(/spl radic/k)/ bits and such that every XOR of outputs has bias 2/sup -n1/(2/spl radic/k)/. We also present a polynomial-time distinguisher for k = 4, m /spl ges/ 24n having constant distinguishing probability. For large values of k we show that a linear distinguisher with a constant distinguishing probability exists once m /spl ges/ /spl Omega/(2/sup k/n/sup [k/2]/). Finally, we consider a variant of the problem where each of the output bits is a degree k polynomial in the inputs. We show there exists a degree k = 2 pseudorandom generator for which the XOR of every subset of the outputs has bias 2/sup -/spl Omega/(n)/ and which map n bits to /spl Omega/(n/sup 2/) bits.

We prove superlinear lower bounds for the number of edges in constant depth circuits with n inputs and up to n outputs. Our lower bounds are proved for all types of constant depth circuits, e.g., constant depth arithmetic circuits and constant depth Boolean circuits with arbitrary gates. The bounds apply for several explicit functions and, most importantly, for matrix product. In particular, we obtain the following results: We show that the number of edges in any constant depth arithmetic circuit for matrix product (over any field) is superlinear in m 2 (where m × m is the size of each matrix). That is, the lower bound is superlinear in the number of input variables. Moreover, if the circuit is bilinear, the result applies also for the case in which the circuit gets any product of two linear functions for free. We show that the number of edges in any constant depth arithmetic circuit for the trace of the product of three matrices (over fields with characteristic 0) is superlinear in m 2 . (Note that the trace is a single-output function.) We give explicit examples for n Boolean functions f 1 ,. . .,f n , such that any constant depth Boolean circuit with arbitrary gates for f 1 ,. . .,f n has a superlinear number of edges. The lower bound is also proved for circuits with arbitrary gates over any finite field. The bound applies for matrix product over finite fields as well as for several other explicit functions.

We prove lower bounds on the number of product gates in bilinear and quadratic circuits that compute the product of two n × n matrices over finite fields. In particular we obtain the following results: We show that the number of product gates in any bilinear (or quadratic) circuit that computes the product of two n × n matrices over ${\rm GF}(2)$ is at least 3n 2 - o(n 2 ). We show that the number of product gates in any bilinear circuit that computes the product of two n × n matrices over ${\rm GF}(q)$ is at least $(2.5 + \frac{1.5}{q^3 -1})n^2 -o(n^2)$. These results improve the former results of [N. H. Bshouty, SIAM J. Comput., 18 (1989), pp. 759-765; M. Bläser, Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Los Alamitos, CA, 1999, pp. 45-50], who proved lower bounds of 2.5 n 2 - o(n 2 ).

We introduce a new model for computing polynomials-a depth 2 circuit with a symmetric gate at the top and plus gates at the bottom, i.e. the circuit computes a symmetric function in linear functions-S/sub m//sup d/(l/sub 1/, l/sub 2/, ..., l/sub m/) (S/sub m//sup d/ is the d'th elementary symmetric polynomial in m variables, and the l/sub i/'s are linear functions). We refer to this model as the symmetric model. This new model is related to standard models of arithmetic circuits, especially to depth 3 circuits. In particular we show that, in order to improve the results of Shpilka and Wigderson (1999), i.e. to prove super-quadratic lower bounds for depth 3 circuits, one must first prove a super-linear lower bound for the symmetric model. We prove two nontrivial linear lower bounds for our model. The first lower bound is for computing the determinant, and the second is for computing the sum of two monomials. The main technical contribution relates the maximal dimension of linear subspaces on which S/sub m//sup d/ vanishes, and lower bounds to the symmetric model. In particular we show that an answer of the following problem (which is very natural, and of independent interest) will imply lower bounds on symmetric circuits for many polynomials: "what is the maximal dimension of a linear subspace of C/sup m/, on which S/sub m//sup d/ vanishes?" We give two partial solutions to the problem above, each enables us to prove a different lower bound.

We prove lower bounds on the number of product gates in bilinear and quadratic circuits that compute the product of two n /spl times/ n matrices over finite fields. In particular we obtain the following results: 1. We show that the number of product gates in any bilinear (or quadratic) circuit that computes the product of two n /spl times/ n matrices over GF(2) is at least 3n/sup 2/ o(n/sup 2/). 2. We show that the number of product gates in any bilinear circuit that computes the product of two n /spl times/ n matrices over GF(p) is at least (2.5 + 1.5/p/sup 3/-1)n/sup 2/ - o(n/sup 2/). These results improve the former results of N.H. Bshouty (1997) and M. Blaser (1999) who proved lower bounds of 2.5n/sup 2/ o(n/sup 2/).

In this paper we prove near quadratic lower bounds for depth-3 arithmetic formulae over fields of characteristic zero. Such bounds are obtained for the elementary symmetric functions, the (trace of) iterated matrix multiplication, and the determinant. As corollaries we get the first non-trivial lower bounds for computing polynomials of constant degree, and a gap between the power depth-3 arithmetic formulas and depth-4 arithmetic formulas. The main technical contribution relates the complexity of computing a polynomial in this model to the wealth of partial derivatives it has on every affine subspace of small co-dimension. Lower bounds for related models utilize an algebraic analog of Nechiporuk lower bound on Boolean formulae.