Read-once polynomial identity testing

ABSTRACT

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(k2) algorithm for checking whether given k ROFs sum to zero or not. An n^O(d+k2) 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+k2) 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²)) 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.

REFERENCES

• 1: M. Agrawal. Proving lower bounds via pseudo-random generators. In 25th FSTTCS, volume 3821 of LNCS, pages 92--105, 2005.
• 2: Dana Angluin , Lisa Hellerstein , Marek Karpinski, Learning read-once formulas with queries, Journal of the ACM (JACM), v.40 n.1, p.185-210, Jan. 1993 [doi>10.1145/138027.138061]
• 3: V. Arvind and P. Mukhopadhyay. The ideal membership problem and polynomial identity testing. ECCC Report TR07-095, 2007.
• 4: 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]
• 5: Andrej Bogdanov , Hoeteck Wee, More on Noncommutative Polynomial Identity Testing, Proceedings of the 20th Annual IEEE Conference on Computational Complexity, p.92-99, June 11-15, 2005 [doi>10.1109/CCC.2005.13]
• 6: Daoud Bshouty , Nader H. Bshouty, On interpolating arithmetic read-once formulas with exponentiation, Journal of Computer and System Sciences, v.56 n.1, p.112-124, Feb. 1998 [doi>10.1006/jcss.1997.1550]
• 7: Nader H. Bshouty , Richard Cleve, Interpolating Arithmetic Read-Once Formulas in Parallel, SIAM Journal on Computing, v.27 n.2, p.401-413, April 1998 [doi>10.1137/S009753979528812X]
• 8: Nader H. Bshouty , Thomas R. Hancock , Lisa Hellerstein, Learning Arithmetic Read-Once Formulas, SIAM Journal on Computing, v.24 n.4, p.706-735, Aug. 1995 [doi>10.1137/S009753979223664X]
• 9: Nader H. Bshouty , Thomas R. Hancock , Lisa Hellerstein, Learning Boolean read-once formulas over generalized bases, Journal of Computer and System Sciences, v.50 n.3, p.521-542, June 1995 [doi>10.1006/jcss.1995.1042]
• 10: 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]
• 11: Zeev Dvir , Amir Shpilka , Amir Yehudayoff, Hardness-randomness tradeoffs for bounded depth arithmetic circuits, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374482]
• 12: 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]
• 13: Thomas Hancock , Lisa Hellerstein, Learning read-once formulas over fields and extended bases, Proceedings of the fourth annual workshop on Computational learning theory, p.326-336, August 05-07, 1991, Santa Cruz, California, United States
• 14: 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]
• 15: M. Karchmer , N. Linial , I. Newman , M. Saks , A. Wigderson, Combinatorial characterization of read-once formulae, Discrete Mathematics, v.114 n.1-3, p.275-282, April 28, 1993 [doi>10.1016/0012-365X(93)90372-Z]
• 16: Zohar S. Karnin , Amir Shpilka, Black Box Polynomial Identity Testing of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-In, Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity, p.280-291, June 22-26, 2008 [doi>10.1109/CCC.2008.15]
• 17: Z. Karnin and A. Shpilka. Interpolating depth-3 arithmetic circuits with bounded topfan-in. Manuscript, 2008.
• 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: B. Lhotzky. On the computational complexity of some algebraic counting problems. Ph.D. thesis, University of Bonn, Department of computer Science, Bonn, Germany, 1991.
• 21: Richard Lipton , Nisheeth Vishnoi, Deterministic identity testing for multivariate polynomials, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 22: 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]
• 23: 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]
• 24: Amir Shpilka, Interpolation of depth-3 arithmetic circuits with two multiplication gates, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250833]
• 25: 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:
Algorithms, Theory

Keywords:
arithmetic circuits, bounded depth circuits, identity testing, read-once formulas, reconstruction