Hardness-randomness tradeoffs for bounded depth arithmetic circuits

ABSTRACT

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₁,...,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₁,...,x_n,y) ≡ 0 and shows that if P has a circuit of depth d and size s and if the polynomial f(x₁,...,x_n) satisfies P(x₁,...,x_n,f(x₁,...,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.

REFERENCES

• 1: M. Agrawal. Proving lower bounds via pseudo-random generators. In Proceedings of the 25th FSTTCS, volume 3821 of Lecture Notes in Computer Science, pages 92--105, 2005.
• 2: 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]
• 3: M. Agrawal, N. Kayal, and N. Saxena. Primes is in P. Annals of Mathematics, 160(2):781--793, 2004.
• 4: V. Arvind and P. Mukhopadhyay. The ideal membership problem and polynomial identity testing. ECCC Report TR07-095, 2007.
• 5: W. Baur and V. Strassen. The complexity of partial derivatives. Theoretical Computer Science, 22:317--330, 1983.
• 6: 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]
• 7: 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]
• 8: Zeev Dvir , Amir Shpilka, Locally Decodable Codes with Two Queries and Polynomial Identity Testing for Depth 3 Circuits, SIAM Journal on Computing, v.36 n.5, p.1404-1434, December 2006 [doi>10.1137/05063605X]
• 9: 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]
• 10: 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]
• 11: D. Grigoriev and A. A. Razborov. Exponential complexity lower bounds for depth $3$ arithmetic circuits in algebras of functions over finite fields. Applicable Algebra in Engineering, Communication and Computing, 10(6):465--487, 2000.
• 12: Russell Impagliazzo , Valentine Kabanets , Avi Wigderson, In search of an easy witness: exponential time vs. probabilistic polynomial time, Journal of Computer and System Sciences, v.65 n.4, p.672-694, December 2002 [doi>10.1016/S0022-0000(02)00024-7]
• 13: Russell Impagliazzo , Ronen Shaltiel , Avi Wigderson, Extractors and pseudo-random generators with optimal seed length, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.1-10, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335306]
• 14: Russell Impagliazzo , Avi Wigderson, P = BPP if E requires exponential circuits: derandomizing the XOR lemma, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.220-229, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258590]
• 15: Valentine Kabanets , Russell Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Computational Complexity, v.13 n.1/2, p.1-46, December 2004 [doi>10.1007/s00037-004-0182-6]
• 16: E. Kaltofen. Factorization of polynomials given by straight-line programs. In S. Micali, editor, Randomness in Computation, volume 5 of Advances in Computing Research, pages 375--412. 1989.
• 17: Z. Karnin and A. Shpilka. Black box polynomial identity testing of generalized depth-3 arithmetic circuits with bounded top fan-in. Manuscript, 2007.
• 18: Neeraj Kayal , Nitin Saxena, Polynomial Identity Testing for Depth 3 Circuits, Computational Complexity, v.16 n.2, p.115-138, May 2007 [doi>10.1007/s00037-007-0226-9]
• 19: 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]
• 20: 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]
• 21: L. Lovasz. On determinants, matchings, and random algorithms. In L. Budach, editor, Fundamentals of Computing Theory. Akademia-Verlag, 1979.
• 22: K. Mulmuley , U. V. Vazirani , V. V. Vazirani, Matching is as easy as matrix inversion, Combinatorica, v.7 n.1, p.105-113, Jan. 1987 [doi>10.1007/BF02579206]
• 23: Noam Nisan , Avi Wigderson, Hardness vs. randomness, Journal of Computer and System Sciences, v.49 n.2, p.149-167, Oct. 1994 [doi>10.1016/S0022-0000(05)80043-1]
• 24: P. Pudlak. Communication in bounded depth circuits. Combinatorica, 14(2):203--216, 1994.
• 25: Ran Raz , Amir Shpilka, Lower Bounds for Matrix Product in Bounded Depth Circuits with Arbitrary Gates, SIAM Journal on Computing, v.32 n.2, p.488-513, 2003 [doi>10.1137/S009753970138462X]
• 26: Ran Raz , Amir Shpilka, Deterministic polynomial identity testing in non-commutative models, Computational Complexity, v.14 n.1, p.1-19, April 2005 [doi>10.1007/s00037-005-0188-8]
• 27: 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]
• 28: Ronen Shaltiel , Christopher Umans, Simple extractors for all min-entropies and a new pseudorandom generator, Journal of the ACM (JACM), v.52 n.2, p.172-216, March 2005 [doi>10.1145/1059513.1059516]
• 29: V. Shoup. New algorithms for finding irreducible polynomials over finite fields. Mathematics of Computation, 54:435--447, 1990.
• 30: Amir Shpilka, Affine projections of symmetric polynomials, Journal of Computer and System Sciences, v.65 n.4, p.639-659, December 2002 [doi>10.1016/S0022-0000(02)00021-1]
• 31: Amir Shpilka , Avi Wigderson, Depth-3 arithmetic circuits over fields of characteristic zero, Computational Complexity, v.10 n.1, p.1-27, 2001 [doi>10.1007/PL00001609]
• 32: V. Strassen. Die Berechnungskomplexiät von elementarsymmetrischenFunktionen und von Interpolationskoeffizienten. Numer. Math., 20:238--251, 1973.
• 33: Madhu Sudan , Luca Trevisan , Salil Vadhan, Pseudorandom generators without the XOR lemma, Journal of Computer and System Sciences, v.62 n.2, p.236-266, March 2001 [doi>10.1006/jcss.2000.1730]
• 34: Seinosuke Toda, PP is as hard as the polynomial-time hierarchy, SIAM Journal on Computing, v.20 n.5, p.865-877, Oct. 1991 [doi>10.1137/0220053]
• 35: 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:
arithmetic circuits, bounded depth circuits, hardness-randomness tradeoffs, identity testing, lower bounds