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

ABSTRACT

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:

1. We show that if E: Fⁿ → F^m is a linear LDC with 2 queries then m = exp(Ω(n)). Previously this was only known for fields of size << 2ⁿ [18].
2. 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).
3. 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).
4. We give new PIT algorithms for ΣΠΣ circuits with a bounded top fan-in:
   1. A deterministic algorithm that runs in quasi polynomial time.
   2. A randomized algorithm that runs in polynomial time and uses only 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)[22, 9, 28]. In particular, for the special case of depth 3 circuits with 3 multiplication gates our result resolves an open question asked by Klivans and Spielman [28].

REFERENCES

• 1: Manindra Agrawal , Somenath Biswas, Primality and identity testing via Chinese remaindering, Journal of the ACM (JACM), v.50 n.4, p.429-443, July 2003 [doi>10.1145/792538.792540]
• 2: Manindra Agrawal, Neeraj Kayal, and Nitin Saxena. Primes is in p, 2002.
• 3: Adi Akavia , Shafi Goldwasser , Samuel Safra, Proving Hard-Core Predicates Using List Decoding, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.146, October 11-14, 2003
• 4: László Babai , Lance Fortnow , Leonid A. Levin , Mario Szegedy, Checking computations in polylogarithmic time, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.21-32, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103428]
• 5: Walter Baur and Volker Strassen. The complexity of partial derivatives. Theoretical Computer Science, 22:317 -- 330, 1983.
• 6: Donald Beaver , J. Feigenbaum, Hiding instances in multioracle queries, Proceedings of the seventh annual symposium on Theoretical aspects of computer science, p.37-48, February 1990, Rouen, France
• 7: Amos Beimel , Yuval Ishai, Information-Theoretic Private Information Retrieval: A Unified Construction, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.912-926, July 08-12, 2001
• 8: Amos Beimel , Yuval Ishai , Eyal Kushilevitz , Jean-François Raymond, Breaking the O(n1/(2k-1)) Barrier for Information-Theoretic Private Information Retrieval, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.261-270, November 16-19, 2002
• 9: Michael Ben-Or, A deterministic algorithm for sparse multivariate polynomial interpolation, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.301-309, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62241]
• 10: Nader H. Bshouty, A lower bound for matrix multiplication, SIAM Journal on Computing, v.18 n.4, p.759-765, Aug. 1989 [doi>10.1137/0218052]
• 11: Suresh Chari , Pankaj Rohatgi , Aravind Srinivasan, Randomness-Optimal Unique Element Isolation withApplications to Perfect Matching and Related Problems, SIAM Journal on Computing, v.24 n.5, p.1036-1050, Oct. 1995 [doi>10.1137/S0097539793250330]
• 12: Zhi-Zhong Chen , Ming-Yang Kao, Reducing randomness via irrational numbers, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.200-209, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258583]
• 13: B. Chor , O. Goldreich , E. Kushilevitz , M. Sudan, Private information retrieval, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.41, October 23-25, 1995
• 14: Amit Deshpande , Rahul Jain , T. Kavitha , Jaikumar Radhakrishnan , Satyanarayana V. Lokam, Better Lower Bounds for Locally Decodable Codes, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.184, May 21-24, 2002
• 15: Joan Feigenbaum , Lance Fortnow, Random-self-reducibility of complete sets, SIAM Journal on Computing, v.22 n.5, p.994-1005, Oct. 1993 [doi>10.1137/0222061]
• 16: Peter Gemmell , Richard Lipton , Ronitt Rubinfeld , Madhu Sudan , Avi Wigderson, Self-testing/correcting for polynomials and for approximate functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.33-42, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103429]
• 17: Peter Gemmell , Madhu Sudan, Highly resilient correctors for polynomials, Information Processing Letters, v.43 n.4, p.169-174, Sept. 28, 1992 [doi>10.1016/0020-0190(92)90195-2]
• 18: Oded Goldreich , Howard Karloff , Leonard J. Schulman , Luca Trevisan, Lower Bounds for Linear Locally Decodable Codes and Private Information Retrieval, Proceedings of the 17th IEEE Annual Conference on Computational Complexity, p.175, May 21-24, 2002
• 19: O. Goldreich , L. A. Levin, A hard-core predicate for all one-way functions, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.25-32, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73010]
• 20: Oded Goldreich , Ronitt Rubinfeld , Madhu Sudan, Learning Polynomials with Queries: The Highly Noisy Case, SIAM Journal on Discrete Mathematics, v.13 n.4, p.535-570, Oct. 2000 to Nov. 2000 [doi>10.1137/S0895480198344540]
• 21: Dima Grigoriev , Marek Karpinski, An exponential lower bound for depth 3 arithmetic circuits, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.577-582, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276872]
• 22: Dima Yu Grigoriev , Marek Karpinski , Michael F. Singer, Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields, SIAM Journal on Computing, v.19 n.6, p.1059-1063, Dec. 1990 [doi>10.1137/0219073]
• 23: D. Grigoriev , A. Razborov, Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.269, November 08-11, 1998
• 24: Mark Jerrum and Marc Snir. Some exact complexity results for straight-line computations over semi-rings. Technical Report CRS-58-80, Univ. of Edinburgh, 1980.
• 25: Valentine Kabanets , Russell Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780595]
• 26: Jonathan Katz , Luca Trevisan, On the efficiency of local decoding procedures for error-correcting codes, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.80-86, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335315]
• 27: Iordanis Kerenidis , Ronald de Wolf, Exponential lower bound for 2-query locally decodable codes via a quantum argument, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780560]
• 28: Adam R. Klivans , Daniel Spielman, Randomness efficient identity testing of multivariate polynomials, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.216-223, July 2001, Hersonissos, Greece [doi>10.1145/380752.380801]
• 29: Leonid A. Levin, One-way functions and Pseudorandom generators, Combinatorica, v.7 n.4, p.357-363, Dec, 1987 [doi>10.1007/BF02579323]
• 30: Daniel Lewin , Salil Vadhan, Checking polynomial identities over any field: towards a derandomization?, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.438-447, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276856]
• 31: Richard J. Lipton, Efficient checking of computations, Proceedings of the seventh annual symposium on Theoretical aspects of computer science, p.207-215, February 1990, Rouen, France
• 32: László Lovász. On determinants, matchings, and random algorithms. In Fundamentals of Comptuation Theory : Proceedings of the Conference on Algebraic, Arithmetic, and Categorial Methods in Computation Theory, volume 2, pages 565--574. Akademie-Verlag, 1979.
• 33: Ketan Mulmuley , Umesh V. Vazirani , Vijay V. Vazirani, Matching is as easy as matrix inversion, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.345-354, January 1987, New York, New York, United States [doi>10.1145/28395.383347]
• 34: Noam Nisan, Lower bounds for non-commutative computation, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.410-418, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103462]
• 35: N. Nisan , A. Wigderson, Lower bounds on arithmetic circuits via partial derivatives, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.16, October 23-25, 1995
• 36: Kenji Obata, Optimal Lower Bounds for 2-Query Locally Decodable Linear Codes, Proceedings of the 6th International Workshop on Randomization and Approximation Techniques, p.39-50, September 13-15, 2002
• 37: Pavel Pudlak. Communication in bounded depth circuits. Combinatorica, 14(2):203--216, 1994.
• 38: Ran Raz, Multi-linear formulas for permanent and determinant are of super-polynomial size, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.633-641, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007353]
• 39: Ran Raz , Amir Shpilka, Deterministic Polynomial Identity Testing in Non-Commutative Models, Proceedings of the 19th IEEE Annual Conference on Computational Complexity, p.215-222, June 21-24, 2004 [doi>10.1109/CCC.2004.11]
• 40: Ran Raz , Amir Shpilka, Lower bounds for matrix product, in bounded depth circuits with arbitrary gates, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.409-418, July 2001, Hersonissos, Greece [doi>10.1145/380752.380833]
• 41: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
• 42: Eli Shamir and Marc Snir. Lower bounds on the number of multiplications and the number of additions in monotone computations. Research Report RC6757, IBM Thomas J. Watson Research Center, Yorktown Heights, N.Y., sep 1977.
• 43: Eli Shamir and Marc Snir. On the depth complexity of formulas. Mathematical Systems Theory, 13:301--322, 1980.
• 44: Amir Shpilka, Lower Bounds for Matrix Product, SIAM Journal on Computing, v.32 n.5, p.1185-1200, 2003 [doi>10.1137/S0097539702405954]
• 45: Amir Shpilka , Avi Wigderson, Depth-3 Arithmetic Formulae over Fields of Characteristic Zero, Proceedings of the Fourteenth Annual IEEE Conference on Computational Complexity, p.87, May 04-06, 1999
• 46: Volker Strassen. Die berechnungskomplexitat vo elementarsymmetrischen funktionen und von interpolationskoefizienten. Numer. Math, 20:238--251, 1973.
• 47: Prasoon Tiwari , Martin Tompa, A direct version of Shamir and Snir's lower bounds on monotone circuit depth, Information Processing Letters, v.49 n.5, p.243-248, March 11, 1994 [doi>10.1016/0020-0190(94)90061-2]
• 48: Luca Trevisan. Some applications of coding theory in computational complexity, 2004.
• 49: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Theory

Keywords:
depth 3 circuits, locally decodable codes, polynomial identity testing