Randomness efficient identity testing of multivariate polynomials

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Randomness efficient identity testing of multivariate polynomials

Full text

Pdf (213 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirty-third annual ACM symposium on Theory of computing table of contents

Hersonissos, Greece

Pages: 216 - 223

Year of Publication: 2001

ISBN:1-58113-349-9

Authors

Adam R. Klivans	Laboratory for Computer Science, MIT, Cambridge, MA
Daniel Spielman	Department of Mathematics, MIT, Cambridge, MA

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 41, Citation Count: 13

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/380752.380801 What is a DOI?

ABSTRACT

We present a randomized polynomial time algorithm to determine if a multivariate polynomial is zero using O(\log mn&dgr;) random bits where n is the number of variables, m is the number of monomials, and &dgr; is the total degree of the unknown polynomial. All other known randomized identity tests (see for example [7, 12, 1]) use &ohgr;(n) random bits even when the polynomial is sparse and has low total degree. In such cases our algorithm has an exponential savings in randomness. In addition, we obtain the first polynomial time algorithm for interpolating sparse polynomials over finite fields of large characteristic. Our approach uses an error correcting code combined with the randomness optimal isolation lemma of [8] and yields a generalized isolation lemma which works with respect to a set of linear forms over a base set.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Manindra Agrawal , Somenath Biswas, Primality and Identity Testing via Chinese Remaindering, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.202, October 17-18, 1999
	2	Sanjeev Arora , Carsten Lund , Rajeev Motwani , Madhu Sudan , Mario Szegedy, Proof verification and the hardness of approximation problems, Journal of the ACM (JACM), v.45 n.3, p.501-555, May 1998 [doi>10.1145/278298.278306]
	3	Noga Alon , Yishay Mansour, &egr;-discrepancy sets and their application for interpolation of sparse polynomials, Information Processing Letters, v.54 n.6, p.337-342, June 23, 1995 [doi>10.1016/0020-0190(95)00032-8]
	4	Sanjeev Arora , Shmuel Safra, Probabilistic checking of proofs: a new characterization of NP, Journal of the ACM (JACM), v.45 n.1, p.70-122, Jan. 1998 [doi>10.1145/273865.273901]
	5	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]
	6	Michael Clausen , Andreas Dress , Johannes Grabmeier , Marek Karpinski, On zero-testing and interpolation of k -sparse multivariate polynomials over finite fields, Theoretical Computer Science, v.84 n.2, p.151-164, July 29, 1991 [doi>10.1016/0304-3975(91)90157-W]
	7	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]
	8	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]
	9	D. Y. Grigoriev and M. Karpinski. The matching problem for bipartite graphs with polynomially bounded permanents is in NC. In Ashok K. Chandra, editor, Proceedings of the 28th Annual Symposium on Foundations of Computer Science, pages 166-172, Los Angeles, CA, October 1987. IEEE Computer Society Press.
	10	Dima Grigoriev , Marek Karpinski , Michael F. Singer, Computational Complexity of Sparse Rational Interpolation, SIAM Journal on Computing, v.23 n.1, p.1-12, Feb. 1994 [doi>10.1137/S0097539791194069]
	11	Marek Karpinski , Igor Shparlinski, On some approximation problems concerning sparse polynomials over finite fields, Theoretical Computer Science, v.157 n.2, p.259-266, May 5, 1996 [doi>10.1016/0304-3975(95)00162-X]
	12	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]
	13	G. L. Miller. Reimann's hypothesis and tests for primality. J. Comput. System Sci, 13:300-317, 1976.
	14	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]
	15	M. O. Rabin. A probabilistic algorithm for testing primality. Journal of Number Theory, 12, 1980.
	16	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]
	17	Adi Shamir, IP = PSPACE, Journal of the ACM (JACM), v.39 n.4, p.869-877, Oct. 1992 [doi>10.1145/146585.146609]
	18	Victor Shoup. Searching for primitive roots in finite fields. Mathematics of Computation, 58(197):369-380, January 1992.
	19	Kai Werther. The complexity of sparse polynomial interpolation over finite fields. Applicable Algebra in Engineering, Communication, and Computing, 5:91-103, 1994.
	20	Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979

CITED BY 13

	Jeff Erickson , Sariel Har-Peled, Optimally cutting a surface into a disk, Proceedings of the eighteenth annual symposium on Computational geometry, p.244-253, June 05-07, 2002, Barcelona, Spain
	Seth Pettie , Vijaya Ramachandran, Minimizing randomness in minimum spanning tree, parallel connectivity, and set maxima algorithms, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.713-722, January 06-08, 2002, San Francisco, California
	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
	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
	Andrej Bogdanov, Pseudorandom generators for low degree polynomials, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Zeev Dvir , Amir Shpilka, Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
	Valentine Kabanets , Russell Impagliazzo, Derandomizing polynomial identity tests means proving circuit lower bounds, Computational Complexity, v.13 n.1/2, p.1-46, January 2004
	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
	Amir Shpilka , Ilya Volkovich, Read-once polynomial identity testing, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada
	Markus Bläser , Moritz Hardt , Richard J. Lipton , Nisheeth K. Vishnoi, Deterministically testing sparse polynomial identities of unbounded degree, Information Processing Letters, v.109 n.3, p.187-192, January, 2009
	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
	Adam R. Klivans , Alexander A. Sherstov, Cryptographic hardness for learning intersections of halfspaces, Journal of Computer and System Sciences, v.75 n.1, p.2-12, January, 2009
	Neeraj Kayal , Nitin Saxena, Polynomial Identity Testing for Depth 3 Circuits, Computational Complexity, v.16 n.2, p.115-138, May 2007