Checking polynomial identities over any field

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Checking polynomial identities over any field: towards a derandomization?

Full text

Pdf (1.32 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the thirtieth annual ACM symposium on Theory of computing table of contents

Dallas, Texas, United States

Pages: 438 - 447

Year of Publication: 1998

ISBN:0-89791-962-9

Authors

Daniel Lewin	Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA
Salil Vadhan	Laboratory for Computer Science, Massachusetts Institute of Technology, 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): 31, Citation Count: 10

Additional Information:

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/276698.276856 What is a DOI?

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.

	ALM+92	S. Arora, C. Lurid, R. Motwani, M. Sudan, and M. Szegedy. Proof verification and hardness of approximation problems. In Proceedings of the Thirty Third Annual Symposium on Foundations of Computer Science, pages 14-23, 1992.
	AS92	S. Arora and S. Safra. Probabilistic checking of proofs. In Proceedings of the Thirty Third Annual Symposium on Foundations of Computer Science, pages 2- 13, 1992.
	BCW80	M. Blum, A.K. Chandra, and M.N. Wegman. Equivalence of free Boolean graphs can be tested in polynomial time. Information Processing Letters, 10:80--.82, 1980.
	BFL90	l.~z16 Babai, Lance Formow, and Carsten Lund. Nondeterministic exponential time has two-prover interactive protocols. In 31st Annual S~mpositan on Foundations of Computer Science, volume I, pages 16..-25, St. Louis, Missouri, 22-24 October 1990. IEEE.
	BK95	Manuel Blum , Sampath Kannan, Designing programs that check their work, Journal of the ACM (JACM), v.42 n.1, p.269-291, Jan. 1995 [doi>10.1145/200836.200880]
	CDGK91	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]
	CK97	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]
	CRS95	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]
	Eis95	David Eisenbud. Commutative Algebra with a View Toward Algebraic Geometry. Graduate Texts in Mathematies 150. Springer-Verlag, 1995.
	GKS90	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]
	Kal82	Erich Kaltofen, A polynomial reduction from multivariate to bivariate integral polynomial factorization., Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.261-266, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802200]
	Kal88	Erich Kaltofen, Greatest common divisors of polynomials given by straight-line programs, Journal of the ACM (JACM), v.35 n.1, p.231-264, Jan. 1988 [doi>10.1145/42267.45069]
	Lan93	Serge Lang. Algebra. Addison-Wesley, 3 edition, 1993.
	LFKN90	C. Lund, L. Fortnow, H. Karlofi, and N. Nisan. Algebraic methods for interactive proofs. In Proceedings of the ThirO, First Annual Sympositan on Foundations of Computer Science, pages 1-10, 1990.
	Lov79	L. Lovasz. On determinants, matehings, and random algorithms. In L. Budach, editor, Fundamentals of Computing Theot3.,. Akademia-Verlag, 1979.
	LV98	Daniel Lewin and Salil Vadhan. Checking polynomial identities over any field: Towards a derandomization7 Available from http: / / theory, lcs .mi t. edu/~danl or http: //www-math.mi t. edu/~salil, 1~98.
	MVV87	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]
	RB91	Ron M. Roth , Gyora M. Benedek, Interpolation and approximation of sparse multivariate polynomials over GF(2), SIAM Journal on Computing, v.20 n.2, p.291-314, April 1990 [doi>10.1137/0220019]
	Sch80	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]
	Sha90	Adi Shamir. IP=PSPACE. In Proceedings ofthe Thirty First Annual Symposium on Foundations of Computer Science, pages 11-15, 1990.
	Str72	V. Strassen. Berechnung und programm I. Acta informatica, 1:320--335, 1972. In German.
	vzGK85	Joachim von zur Gathen , Erich Kaltofen, Factoring sparse multivariate polynomials, Journal of Computer and System Sciences, v.31 n.2, p.265-287, Sept. 1985 [doi>10.1016/0022-0000(85)90044-3]
	Zip79	Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979
	Zip81	Richard Zippel, Newton's iteration and the sparse Hensel algorithm (Extended Abstract), Proceedings of the fourth ACM symposium on Symbolic and algebraic computation, p.68-72, August 05-07, 1981, Snowbird, Utah, United States [doi>10.1145/800206.806372]

CITED BY 11

	Satyanarayana V. Lokam, Complexity Lower Bounds using Linear Algebra, Foundations and Trends® in Theoretical Computer Science, v.4 n.1–2, p.1-155, January 2009
	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
	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
	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
	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
	Michel X. Goemans , David P. Williamson, Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming, Journal of Computer and System Sciences, v.68 n.2, p.442-470, March 2004
	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
	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
	Neeraj Kayal , Nitin Saxena, Polynomial Identity Testing for Depth 3 Circuits, Computational Complexity, v.16 n.2, p.115-138, May 2007