Amir Shpilka

STOC Conference 2021 Invited Paper

Learnability can be independent of set theory (invited paper)

• Shai Ben-David
• Pavel Hrubes
• Shay Moran
• Amir Shpilka
• Amir Yehudayoff

STOC Conference 2021 Conference Paper

Polynomial time deterministic identity testing algorithm for Σ [3] ΠΣΠ [2] circuits via Edelstein-Kelly type theorem for quadratic polynomials

• Shir Peleg
• Amir Shpilka

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.

SODA Conference 2020 Conference Paper

On the Performance of Reed-Muller Codes with respect to Random Errors and Erasures

• Ori Sberlo
• Amir Shpilka

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 = 2 m 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].

STOC Conference 2019 Conference Paper

Sylvester-Gallai type theorems for quadratic polynomials

• Amir Shpilka

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 Q 1 , Q 2 ∈ Q there is a third polynomial Q 3 ∈ Q so that whenever Q 1 and Q 2 vanish then also Q 3 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. This answers affirmatively two conjectures of Gupta [Electronic Colloquium on Computational Complexity (ECCC), 21:130, 2014] that were raised in the context of solving certain depth-4 polynomial identities. To obtain our main theorems we prove a new result classifying the possible ways that a quadratic polynomial Q can vanish when two other quadratic polynomials vanish. Our proofs also require robust versions of a theorem of Edelstein and Kelly (that extends the Sylvester-Gallai theorem to colored sets).

STOC Conference 2018 Conference Paper

A PSPACE construction of a hitting set for the closure of small algebraic circuits

• Michael A. Forbes 0001
• Amir Shpilka

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. The proof relies on the new notion of a robust hitting set which is a set of inputs such that any nonzero polynomial that can be computed by a polynomial size algebraic circuit, evaluates to a not too small value on at least one element of the set. Proving the existence of such a robust hitting set is the main technical difficulty in the proof. Our proof uses anti-concentration results for polynomials, basic tools from algebraic geometry and the existential theory of the reals.

STOC Conference 2017 Conference Paper

Succinct hitting sets and barriers to proving algebraic circuits lower bounds

• Michael A. Forbes 0001
• Amir Shpilka
• Ben Lee Volk

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. Following a similar result of Williams in the boolean setting, we show that the existence of an algebraic natural proofs barrier is equivalent to the existence of succinct derandomization of the polynomial identity testing problem. That is, whether the coefficient vectors of polylog(N)-degree polylog(N)-size circuits is a hitting set for the class of poly(N)-degree poly(N)-size circuits. Further, we give an explicit universal construction showing that if such a succinct hitting set exists, then our universal construction suffices. Further, we assess the existing literature constructing hitting sets for restricted classes of algebraic circuits and observe that none of them are succinct as given. Yet, we show how to modify some of these constructions to obtain succinct hitting sets. This constitutes the first evidence supporting the existence of an algebraic natural proofs barrier. Our framework is similar to the Geometric Complexity Theory (GCT) program of Mulmuley and Sohoni, except that here we emphasize constructiveness of the proofs while the GCT program emphasizes symmetry. Nevertheless, our succinct hitting sets have relevance to the GCT program as they imply lower bounds for the complexity of the defining equations of polynomials computed by small circuits.

STOC Conference 2016 Conference Paper

Efficiently decoding Reed-Muller codes from random errors

• Ramprasad Saptharishi
• Amir Shpilka
• Ben Lee Volk

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 2 m − 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 work we give an efficient algorithm (in the block length n =2 m ) for decoding random errors in Reed-Muller codes far beyond the minimal 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 m r /2 errors. More generally, for any integer r , our algorithm can correct any error pattern in RM ( m , m −(2 r +2)) for which the same erasure pattern can be corrected in RM ( m , m −( r +1)). The results above are obtained by applying recent results of Abbe, Shpilka and Wigderson (STOC, 2015), Kumar and Pfister (2015) and Kudekar et al. (2015) regarding the ability of Reed-Muller 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 Reed-Muller 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 famous Berlekamp-Welch algorithm for decoding Reed-Solomon codes.

FOCS Conference 2015 Conference Paper

Compressing and Teaching for Low VC-Dimension

• Shay Moran
• Amir Shpilka
• Avi Wigderson
• Amir Yehudayoff

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.

STOC Conference 2015 Conference Paper

Reed-Muller Codes for Random Erasures and Errors

• Emmanuel Abbe
• Amir Shpilka
• Avi Wigderson

STOC Conference 2014 Conference Paper

Hitting sets for multilinear read-once algebraic branching programs, in any order

• Michael A. Forbes 0001
• Ramprasad Saptharishi
• Amir Shpilka

We give deterministic black-box polynomial identity testing algorithms for multilinear read-once oblivious algebraic branching programs (ROABPs), in n O (log 2 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. We obtain our results by recasting, and improving upon, the ideas of Agrawal, Saha and Saxena [ASS13]. We phrase the ideas in terms of rank condensers and Wronskians , and show that our results improve upon the classical multivariate Wronskian, which may be of independent interest. In addition, we give the first n O (lg lg n ) black-box polynomial identity testing algorithm for the so called model of diagonal circuits. This result improves upon the n Θ(lg n ) -time algorithms given by Agrawal, Saha and Saxena [ASS13], and Forbes and Shpilka [FS13b] for this class. More generally, our result holds for any model computing polynomials whose partial derivatives (of all orders) span a low dimensional linear space.

FOCS Conference 2013 Conference Paper

Quasipolynomial-Time Identity Testing of Non-commutative and Read-Once Oblivious Algebraic Branching Programs

• Michael A. Forbes 0001
• Amir Shpilka

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

STOC Conference 2012 Conference Paper

On identity testing of tensors, low-rank recovery and compressed sensing

• Michael A. Forbes 0001
• Amir Shpilka

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(rn 2 +r 3 n) 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. We also give a more formal connection between low-rank recovery and the task of sparse (vector) recovery : any sparse-recovery algorithm that exactly recovers vectors of length n and sparsity 2r, using m non-adaptive measurements, yields a low-rank recovery scheme for exactly recovering n x n matrices of rank ≤ r, making 2nm non-adaptive measurements. Furthermore, if the sparse-recovery algorithm runs in time τ, then the low-rank recovery algorithm runs in time O(rn 2 +nτ). We obtain this reduction using linear-algebraic techniques, and not using convex optimization, which is more commonly seen in compressed sensing algorithms. Finally, we also make a connection to rank-metric codes , as studied in coding theory. These are codes with codewords consisting of matrices (or tensors) where the distance of matrices M and N is rank(M-N), as opposed to the usual hamming metric. We obtain essentially optimal-rate codes over matrices, and provide an efficient decoding algorithm. We obtain codes over tensors as well, with poorer rate, but still with efficient decoding.

FOCS Conference 2011 Conference Paper

Optimal Testing of Multivariate Polynomials over Small Prime Fields

• Elad Haramaty
• Amir Shpilka
• Madhu Sudan 0001

We consider the problem of testing if a given function f: F q n →F q is close to a n-variate degree d polynomial over the finite field F q of q elements. The natural, low-query, test for this property would be to pick the smallest dimension t = t q, d ≈ d/q such that every function of degree greater than d reveals this aspect on some i-dimensional affine subspace of F q n and 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 q t queries, 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 q 2t queries. Kaufman and Ron also noted that when q is prime, then q t queries 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(q tq-d ) - which is tight to within constant factors.

FOCS Conference 2011 Conference Paper

Tight Lower Bounds for 2-query LCCs over Finite Fields

• Arnab Bhattacharyya 0001
• Zeev Dvir
• Amir Shpilka
• Shubhangi Saraf

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.

STOC Conference 2010 Conference Paper

Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in

• Zohar Shay Karnin
• Partha Mukhopadhyay
• Amir Shpilka
• Ilya Volkovich

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

STOC Conference 2010 Conference Paper

On the structure of cubic and quartic polynomials

• Elad Haramaty
• Amir Shpilka

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) F n 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.

FOCS Conference 2010 Conference Paper

Pseudorandom Generators for CC0[p] and the Fourier Spectrum of Low-Degree Polynomials over Finite Fields

• Shachar Lovett
• Partha Mukhopadhyay
• Amir Shpilka

In this paper we give the first construction of a pseudorandom generator, with seed length O(log n), for CC 0 [p], the class of constant-depth circuits with unbounded fan-in MOD p gates, 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 F p, 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 F p, 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 F p. Then, for every ϵ > 0 there exists a subset S ⊂ [n], whose size depends only on d and ϵ, such that Σ α∈F p n: α≠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 F p. 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.

STOC Conference 2009 Conference Paper

Explicit construction of a small epsilon-net for linear threshold functions

• Yuval Rabani
• Amir Shpilka

STOC Conference 2008 Conference Paper

Hardness-randomness tradeoffs for bounded depth arithmetic circuits

• Zeev Dvir
• Amir Shpilka
• Amir Yehudayoff

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(x 1 ,...,x m ) that cannot be computed by a depth d arithmetic circuit of small size then there exists an efficient deterministic algorithm to test whether a given depth d-8 circuit is identically zero or not (assuming the individual degrees of the tested circuit are not too high). In particular, if we are guaranteed that the circuit computes a multilinear polynomial then we can perform the identity test efficiently. To the best of our knowledge this is the first hardness-randomness tradeoff for bounded depth arithmetic circuits. The above results are obtained using the arithmetic Nisan-Wigderson generator of Impagliazzo and Kabanets together with a new theorem on bounded depth circuits, which is the main technical contribution of our work. This theorem deals with polynomial equations of the form P(x 1 ,...,x n ,y) ≡ 0 and shows that if P has a circuit of depth d and size s and if the polynomial f(x 1 ,...,x n ) satisfies P(x 1 ,...,x n ,f(x 1 ,...,x n ))≡ 0 then f has a circuit of depth d+3 and size O(s • r + m r ), where m is the degree of f and r is the highest degree of the variable y appearing in P. In the other direction we observe that the methods of Impagliazzo and Kabanets imply that if we can derandomize polynomial identity testing for bounded depth circuits then NEXP does not have bounded depth arithmetic circuits. That is, either NEXP ⊄ P/poly or the Permanent is not computable by polynomial size bounded depth arithmetic circuits.

STOC Conference 2008 Conference Paper

Read-once polynomial identity testing

• Amir Shpilka
• Ilya Volkovich

In this paper we study the problems of polynomial identity testing (PIT) and reconstruction of read-once formulas. The following are some deterministic algorithms that we obtain. An n O(k 2 ) algorithm for checking whether given k ROFs sum to zero or not. An n O(d+k 2 ) time algorithm for checking whether a black box holding the sum of k depth d ROFs computes the zero polynomial. In other words, we provide a hitting set of size n O(d+k 2 ) for the sum of k depth d ROFs. This implies an n O(d) deterministic algorithm for the reconstruction of depth d ROFs. A hitting set of size exp(~O(√n+k 2 )) for the sum of k ROFs (without depth restrictions). This implies a sub-exponential time deterministic algorithm for black-box identity testing and reconstructing of ROFs. To the best of our knowledge our results give the first polynomial time (non black-box) and sub-exponential time (black-box) identity testing algorithms for the sum of (a constant number of) ROFs. In addition, we introduce and study the read-once testing problem (ROT for short): Given an arithmetic circuit computing a polynomial P(x), decide whether there is a ROF computing P(x). If there is such a formula then output it. Otherwise output "No". We show that most previous algorithms for polynomial identity testing can be strengthen to yield algorithms for the ROT problem. In particular we give ROT algorithms for: Depth-2 circuits (circuits computing sparse polynomials), Depth-3 circuits with bounded top fan-in (both in the black-box and non black-box settings, where the running time depends on the model), non-commutative formulas and sum of k ROFs. The running time of the ROT algorithm is essentially the same running time as the corresponding PIT algorithm for the class. The main tool in most of our results is a new connection between polynomial identity testing and reconstruction of read-once formulas. Namely, we show that in any model that is closed under partial derivatives (that is, a partial derivative of a polynomial computed by a circuit in the model, can also be computed by a circuit in the model) and that has an efficient deterministic polynomial identity testing algorithm, we can also answer the read-once testing problem.

FOCS Conference 2007 Conference Paper

A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

• Ran Raz
• Amir Shpilka
• Amir Yehudayoff

We construct an explicit polynomial f(x 1, .. ., 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 2 n} The lower bound holds over any field.

STOC Conference 2007 Conference Paper

Interpolation of depth-3 arithmetic circuits with two multiplication gates

• Amir Shpilka

FOCS Conference 2007 Conference Paper

Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem

• Sofya Raskhodnikova
• Dana Ron
• Amir Shpilka
• Adam Smith 0006

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. X 1 and X 2, with very different expectations and the following condition on the first k moments: E[X 1 ]/E[X 2 ] = E[X 1 2 ]/E[X 2 2 ] =. .. = E[X 1 k ]/E[X 2 k ]. 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.

STOC Conference 2005 Conference Paper

Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits

• Zeev Dvir
• Amir Shpilka

In this work we study two, seemingly unrelated, notions. Locally Decodable Codes (LDCs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. Polynomial Identity Testing (PIT) is one of the fundamental problems of algebraic complexity: we are given a circuit computing a multivariate polynomial and we have to determine whether the polynomial is identically zero. We improve known results on locally decodable codes and on polynomial identity testing and show a relation between the two notions. In particular we obtain the following results: We show that if E: Fn → Fm is a linear LDC with 2 queries then m = exp(Ω(n)). Previously this was only known for fields of size << 2n [18]. We show that from every depth 3 arithmetic circuit (ΣΠΣ circuit), C, with a bounded (constant) top fan-in that computes the zero polynomial, one can construct a locally decodeable code. More formally: Assume that C is minimal (no subset of the multiplication gates sums to zero) and simple (no linear function appears in all the multiplication gates). Denote by d the degree of the polynomial computed by C and by r the rank of the linear functions appearing in C. Then we can construct a linear LDC with 2 queries, that encodes messages of length r/polylog(d) by codewords of length O(d). We prove a structural theorem for ΣΠΣ circuits, with a bounded top fan-in, that compute the zero polynomial. In particular we show that if such a circuit is simple and minimal and of polynomial size then its rank, r, is only polylogarithmic in the number of variables (a priory it could have been linear). We give new PIT algorithms for ΣΠΣ circuits with a bounded top fan-in:A deterministic algorithm that runs in quasi polynomial time.A randomized algorithm that runs in polynomial time and uses only polylogarithmic number of random bits.

STOC Conference 2004 Conference Paper

Derandomizing homomorphism testing in general groups

• Amir Shpilka
• Avi Wigderson

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 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 the recent result of [12], who proved such a result only for the groups G=Z p m and Γ=Z p . 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.

FOCS Conference 2003 Conference Paper

Locally Testable Cyclic Codes

• László Babai
• Amir Shpilka
• Daniel Stefankovic

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.

FOCS Conference 2003 Conference Paper

On e-Biased Generators in NC0

• Elchanan Mossel
• Amir Shpilka
• Luca Trevisan 0001

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.

FOCS Conference 2001 Conference Paper

Lower Bounds for Matrix Product

• Amir Shpilka

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/).

STOC Conference 2001 Conference Paper

Lower bounds for matrix product, in bounded depth circuits with arbitrary gates

• Ran Raz
• Amir Shpilka

We prove super-linear 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 super-linear in m^2 (where m \times m is the size of each matrix). That is, the lower bound is super-linear in the number of input variables. Moreover, if the circuit is bilinear the result applies also for the case where the circuit gets for free any product of two linear functions. We show that the number of edges in any constant depth arithmetic circuit for the trace of the product of 3 matrices (over fields with characteristic~0) is super-linear in m^2 . (Note that the trace is a single-output function). We give explicit examples for n Boolean functions f_1,\dots,f_ , such that any constant depth Boolean circuit with arbitrary gates for f_1,...,f_n has a super-linear number of edges. The lower bound is proved also 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.