On a special case of rigidity.

We highlight the special case of Valiant’s rigidity problem in which the low-rank matrices are truth-tables of sparse polynomials. We show that progress on this special case entails that Inner Product is not computable by small AC circuits with one layer of parity gates close to the inputs. We then prove that the sign of any −1/1 polynomial with ≤ s monomials in 2n variables disagrees with Inner Product in ≥ Ω(1/s) fraction of inputs, a type of result that seems unknown in the rigidity setting. Valiant’s rigidity problem [Val77] asks to build explicit matrixes that are far in Hamming distance from low-rank matrixes. Valiant proved that if an N ×N matrix M has hamming distance ≥ N from any matrix of rank R = (1−Ω(1))N , then the corresponding linear transformation x 7→ Mx requires circuits of superlogarithmic depth or superlinear size. Exhibiting an explicit such matrix remains a long-standing challenge. Despite significant efforts, the best lower bounds are of the form (N/R) lg(N/R) against matrixes of rank R. The matrix corresponding to the inner product function IP has been conjectured to satisfy better better bounds. We refer the reader to Lokam’s survey [Lok09] for more on rigidity. In this note we highlight a special case of the rigidity problem, and we suggest that attacks should be directed towards it. Recall that an N ×N matrix has rank R if and only if it is the sum of R rank-1 matrixes, i.e., matrixes uiv T i , where ui, vi are N -entry column vectors. We consider the special case of this problem where the rank-1 matrixes are the truthtables of monomials over the variables x1, . . . , xn, y1, . . . , yn, where N = 2 n and the variables range over {−1, 1}. For example, the truth-table of a monomial c ∏ i∈S xi ∏ i∈T yi, where S, T ⊆ {1, . . . , n}, is the N ×N matrix whose entry indexed by (a, b) ∈ {−1, 1}×{−1, 1} is c ∏ i∈S ai ∏ i∈T bi. This matrix can be written as uv T where the a-th entry of u is c ∏ i∈S ai and the b-th entry of v is ∏ i∈T bi. This special case of the rigidity problem is stated without direct reference to rank as follows. Challenge 0.1 (Sparsity). Exhibit an explicit function f : {−1, 1} × {−1, 1} → {−1, 1} such that for any real polynomial p with ≤ R monomials we have Pr x,y∈{−1,1}n [f(x, y) 6= p(x, y)] ≥ , ∗Supported by NSF grant CCF-1115703. Email: rocco@cs.columbia.edu †Supported by NSF grant CCF-0845003. Email: viola@ccs.neu.edu for as large as possible. Again, = Ω(lg(2/R)/R) follows from the rigidity bounds. The concurrent work [RV12] raises a similar challenge for low-degree (as opposed to sparse) polynomials. Motivation: AC with parity gates. Besides hopefully paving the way for the original rigidity question, a motivation for making progress on Challenge 0.1 is that stronger bounds would yield new circuit lower bounds. Let AC-⊕ denote the class of AC circuits augmented with a bottom level (right before the input bits) of parity gates. To our knowledge, it is not known whether the Inner Product function IP is computable by poly-size AC-⊕ circuits: Challenge 0.2. Show that IP cannot be computed by poly-size AC-⊕ circuits. Challenge 0.2 seems open even for AC-⊕ circuits of depth 4, but it is known to be true for AC-⊕ circuits of depth 3, i.e. poly-size DNF-⊕ circuits. Indeed, it follows from Fact 8 in [Jac97] that any function computable by such circuits has 1/poly correlation with parity on some subset of the variables, but it is well-known that IP has exponentially small correlation with parity on any subset of the variables. Solving Challenge 0.2 is a step towards a more thorough understanding of AC with parity gates. For example, no strong correlation bound is known for this class, see e.g. [SV10]. In fact, this is not even known for AC-⊕, and IP is a natural candidate. Next we formally connect the two challenges. Claim 0.3. Suppose that IP on 2n variables has AC-⊕ circuits of polynomial size. Then for any b there exists c and a polynomial p(x, y) with ≤ 2lgc n monomials such that Pr x,y [p(x, y) 6= IP(x, y)] ≤ 2lgb . Proof. Let C be a depth-(d+1) AC-⊕ circuit that computes IP over 2n input bits x1, . . . , xn, y1, . . . , yn. Let N = poly(n) denote the number of parity gates at the leaves. Let C ′ be the depth-d AC circuit obtained by replacing the i-th parity gate by a fresh input variable zi (so C ′ is a circuit over N input bits z1, ..., zN). Let D be the distribution over {−1, 1} induced by drawing a uniform random input x from {−1, 1} and setting zi = the value of the i-th parity gate on x (the draw from D is the string z ∈ {0, 1}). Let := 1/2lgc . Lemma 5.1 and Corollary 5.2 of [ABFR94] tell us that there is a polynomial p(z1, . . . , zN) of degree (O(lg(n)) 2d that computes C ′(z) for a (1 − ) fraction of all inputs drawn from D. Since p has degree (O(lg n)) it must have ≤ n n))2d monomials. Now let q(x1, ..., xn, y1, . . . , yn) be the polynomial obtained by substituting in the i-th parity (monomial) for zi in p. q has no more monomials than p, and q computes IP on (1− ) fraction of all inputs drawn from {−1, 1}. We note that for Valiant’s connection to lower bounds, we need rank R = Ω(N), whereas for sparsity much smaller rank R = poly lgN suffices. In both cases we need to go beyond error 1/R.