Fast Probabilistic Algorithms for Verification of Polynomial Identities

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Fast Probabilistic Algorithms for Verification of Polynomial Identities

Full text

Pdf (1.13 MB)

Source

Journal of the ACM (JACM) archive
Volume 27 , Issue 4 (October 1980) table of contents

Pages: 701 - 717

Year of Publication: 1980

ISSN:0004-5411

Author

J. T. Schwartz

Computer Science Department, Courant Institute of Mathematical Sciences, New York University, 251 Mercer Street, New York, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 33, Downloads (12 Months): 211, Citation Count: 144

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/322217.322225 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.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	BIEBERBACH, L, AND BAUER, G Vorlesungen uber Algebra. B G Teubner Pubhshmg Co, Berhn, 1928.
	3	CHAITIN, G., AND SCHWARTZ, J.T. A note on Monte Carlo pmnallty tests and algorithmic reformation theory Commun Pure Appl Math. (1978)
	4	George E. Collins, The Calculation of Multivariate Polynomial Resultants, Journal of the ACM (JACM), v.18 n.4, p.515-532, Oct. 1971 [doi>10.1145/321662.321666]
	5	COLLINS, G.E Computer algebra of polynomials and rattonal functions Amer. Math Monthly 80 (1973), 725-753
	6	Philip J. Davis, Proof, Completeness, Transcendentals, and Sampling, Journal of the ACM (JACM), v.24 n.2, p.298-310, April 1977 [doi>10.1145/322003.322013]
	7	DUNFORD, N., AND SCHWARTZ, J T Linear Operators, Part II. Wfiey-lntersclence, New York and London, 1963.
	8	FEKETE, M.uber dte Verteilung der Wurzeln bet Gew~ssen Algebraischen Glelchungen mit Ganzzahligen Koeffiztenten Math. Z. 17 (1927), 228-249.
	9	FEKETE, M, AND SZEGO, G. On algebratc equations with integer coefficients whose roots belong to a given point set Math. Z. 63 (1955), 158-172
	10	Lee E. Heindel, Integer Arithmetic Algorithms for Polynomial Real Zero Determination, Journal of the ACM (JACM), v.18 n.4, p.533-548, Oct. 1971 [doi>10.1145/321662.321667]
	11	HERMANN, G. D~e Frage der Endlich Vtelen Schntte m der Theorie der Polynomidealen. Math. Ann. 95 (1926), 736-788
	12	KAKEYA, S On approximate polynomials Tohoku Math J. 6 (1914), 182-186.
	13	William A. Martin, Determining the Equivalence of Algebraic Expressions by Hash Coding, Journal of the ACM (JACM), v.18 n.4, p.549-558, Oct. 1971 [doi>10.1145/321662.321668]
	14	R. T. Moenck, Fast computation of GCDs, Proceedings of the fifth annual ACM symposium on Theory of computing, p.142-151, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804045]
	15	OKADA, Y On approximate polynomials with integer co~ffictents only Tohoku Math. Z 23 (1924), 26-35.
	16	POLYA, G, ANn SZEGO, G Problems and Theorems in Analysis, vol 2 Sprmger-Vedag, New York, 1976.
	17	RAaIN, M. Probabdtsttc algorithms In Algorithms and Complextty. New D:reclions and Recent Result.~ J.F. Traub, Ed, Academic Press, New York, 1976, pp. 21-39
	18	SEIDENBERG, A.A new decision method for elementary algebra. Ann. Math. 60 (1954), 365-374.
	19	TARSKI, A Declston Methodfor Elementary Algebra and Geometry, 2nd ed. University of California Press, Berkeley, Cahf., 1951.
	20	VAN DER WAERDEN, B.L. Modern Algebra, vols. I, 11. Fredenck Ungar Publishing Co., New York, 1949, 1950.
	21	VAN DER WAERDEN, B L.Emfuhrung m die Algebralsche Geometne, 2nd ed. Springer Verlag, New York, 1973

CITED BY 144

	Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998
	Jacob Katzenelson , Shlomit S. Pinter , Eugen Schenfeld, Type matching, type-graphs, and the Schanuel conjecture, ACM Transactions on Programming Languages and Systems (TOPLAS), v.14 n.4, p.574-588, Oct. 1992
	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
	L. W. Ericson , C. K. Yap, The design of LINETOOL, a geometric editor, Proceedings of the fourth annual symposium on Computational geometry, p.83-92, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	U Vazirani , V V Vazirani, The two-processor scheduling problem is in R-NC, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.11-21, May 06-08, 1985, Providence, Rhode Island, United States
	Mikael Rittri, Using types as search keys in function libraries, Proceedings of the fourth international conference on Functional programming languages and computer architecture, p.174-183, September 11-13, 1989, Imperial College, London, United Kingdom
	Victor Y. Pan , Isdor Sobze , Antoine Atinkpahoun, Optimum parallel computations with banded matrices, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.649-658, January 23-25, 1994, Arlington, Virginia, United States
	Katalin Friedl , Zsolt Hátsági , Alexander Shen, Low-degree tests, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.57-64, January 23-25, 1994, Arlington, Virginia, United States
	Gudmund Skovbjerg Frandsen , Johan P. Hansen , Peter Bro Miltersen, Lower bounds for dynamic algebraic problems, Information and Computation, v.171 n.2, p.333-349, December 15, 2001
	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
	Mark Giesbrecht, Efficient parallel solution of sparse systems of linear diophantine equations, Proceedings of the second international symposium on Parallel symbolic computation, p.1-10, July 20-22, 1997, Maui, Hawaii, United States
	Sanjeev Arora , Madhu Sudan, Improved low-degree testing and its applications, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.485-495, May 04-06, 1997, El Paso, Texas, United States
	T. Freeman , G. Imirzian , E. Kaltofen, A system for manipulating polynomials given by straight-line programs, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.169-175, July 21-23, 1986, Waterloo, Ontario, Canada
	Chanderjit L. Bajaj, Geometric computations with algebraic varieties of bounded degree, Proceedings of the sixth annual symposium on Computational geometry, p.148-156, June 07-09, 1990, Berkley, California, United States
	Oscar H. Ibarra , Shlomo Moran, Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs, Journal of the ACM (JACM), v.30 n.1, p.217-228, Jan. 1983
	Michael Kaminski, A note on probabilistically verifying integer and polynomial products, Journal of the ACM (JACM), v.36 n.1, p.142-149, Jan. 1989
	E Kaltofen, Computing with polynomials given by straight-line programs I: greatest common divisors, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.131-142, May 06-08, 1985, Providence, Rhode Island, United States
	Joseph Cheriyan, Random Weighted Laplacians, Lovász minimum digraphs and finding minimum separators, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.31-40, January 25-27, 1993, Austin, Texas, United States
	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
	Arne Storjohann , George Labahn, Preconditioning of rectangular polynomial matrices for efficient Hermite normal form computation, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.119-125, July 10-12, 1995, Montreal, Quebec, Canada
	Joseph Cheriyan, A Las Vegas O(n2.38 algorithm for the cardinality of a maximum matching, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.442-451, January 23-25, 1994, Arlington, Virginia, United States
	Gaston H. Gonnet, New results for random determination of equivalence of expressions, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.127-131, July 21-23, 1986, Waterloo, Ontario, Canada
	P. A. Bloniarz , H. B. Hunt, III , D. J. Rosenkrantz, Algebraic Structures with Hard Equivalence and Minimization Problems, Journal of the ACM (JACM), v.31 n.4, p.879-904, Oct. 1984
	Gaston H. Gonnet, Determining equivalence of expressions in random polynomial time, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.334-341, December 1984
	S. S. Abhyankar , C. J. Bajaj, Automatic parameterization of rational curves and surfaces IV: algebraic space curves, ACM Transactions on Graphics (TOG), v.8 n.4, p.325-334, Oct. 1989
	C. Bajaj , J. Canny , R. Garrity , J. Warren, Factoring rational polynomials over the complexes, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.81-90, July 17-19, 1989, Portland, Oregon, United States
	Mark Giesbrecht, Fast computation of the Smith normal form of an integer matrix, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.110-118, July 10-12, 1995, Montreal, Quebec, Canada
	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
	Erich Kaltofen, Asymptotically fast solution of Toeplitz-like singular linear systems, Proceedings of the international symposium on Symbolic and algebraic computation, p.297-304, July 20-22, 1994, Oxford, United Kingdom
	Uriel Feige , Carsten Lund, On the hardness of computing the permanent of random matrices (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.643-654, May 04-06, 1992, Victoria, British Columbia, Canada
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	D. Grigoriev, Testing shift-equivalence of polynomials using quantum machines, Proceedings of the 1996 international symposium on Symbolic and algebraic computation, p.49-54, July 24-26, 1996, Zurich, Switzerland
	Joseph Cheriyan , John H. Reif, Directed s-t numberings, rubber bands, and testing digraph k-vertex connectivity, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.335-344, September 1992, Orlando, Florida, United States
	Nader H. Bshouty, On the complexity of functions for random access machines, Journal of the ACM (JACM), v.40 n.2, p.211-223, April 1993
	J. F. Canny , E. Kaltofen , L. Yagati, Solving systems of nonlinear polynomial equations faster, Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computation, p.121-128, July 17-19, 1989, Portland, Oregon, United States
	Hal Wasserman , Manuel Blum, Software reliability via run-time result-checking, Journal of the ACM (JACM), v.44 n.6, p.826-849, Nov. 1997
	Victor Y. Pan , Zhao Q. Chen, The complexity of the matrix eigenproblem, Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.507-516, May 01-04, 1999, Atlanta, Georgia, United States
	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
	Felipe Cucker , Marek Karpinski , Pascal Koiran , Thomas Lickteig , Kai Werther, On real Turing machines that toss coins, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.335-342, May 29-June 01, 1995, Las Vegas, Nevada, United States
	László Babai , Katalin Friedl , Markus Stricker, Decomposition of *-closed algebras in polynomial time, Proceedings of the 1993 international symposium on Symbolic and algebraic computation, p.86-94, July 06-08, 1993, Kiev, Ukraine
	Michael B. Monagan , Gaston H. Gonnet, Signature functions for algebraic numbers, Proceedings of the international symposium on Symbolic and algebraic computation, p.291-296, July 20-22, 1994, Oxford, United Kingdom
	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
	John F. Canny , Ioannis Z. Emiris, A subdivision-based algorithm for the sparse resultant, Journal of the ACM (JACM), v.47 n.3, p.417-451, May 2000
	H. Narayanan , Huzur Saran , Vijay V. Vazirani, Randomized parallel algorithms for matroid union and intersection, with applications to arboresences and edge-disjoint spanning trees, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.357-366, September 1992, Orlando, Florida, United States
	M. Giesbrecht , A. Lobo , B. D. Saunders, Certifying inconsistency of sparse linear systems, Proceedings of the 1998 international symposium on Symbolic and algebraic computation, p.113-119, August 13-15, 1998, Rostock, Germany
	Wayne Eberly , Erich Kaltofen, On randomized Lanczos algorithms, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.176-183, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	Nader H. Bshouty , Thomas R. Hancock , Lisa Hellerstein, Learning arithmetic read-once formulas, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.370-381, May 04-06, 1992, Victoria, British Columbia, Canada
	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
	Alexander Chistov , Gábor Ivanyos , Marek Karpinski, Polynomial time algorithms for modules over finite dimensional algebras, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.68-74, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	Daoud Bshouty , Nader H. Bshouty, On learning arithmetic read-once formulas with exponentiation (extended abstract), Proceedings of the seventh annual conference on Computational learning theory, p.311-317, July 12-15, 1994, New Brunswick, New Jersey, United States
	John H. Reif, O(log2 n) time efficient parallel factorization of dense, sparse separable, and banded matrices, Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.278-289, June 27-29, 1994, Cape May, New Jersey, United States
	Angel Díaz , Erich Kaltofen, On computing greatest common divisors with polynomials given by black boxes for their evaluations, Proceedings of the 1995 international symposium on Symbolic and algebraic computation, p.232-239, July 10-12, 1995, Montreal, Quebec, Canada
	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
	Sergei A. Abramov , Manuel Bronstein, On solutions of linear functional systems, Proceedings of the 2001 international symposium on Symbolic and algebraic computation, p.1-6, July 2001, London, Ontario, Canada
	Victor Y. Pan, Nearly optimal computations with structured matrices, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.953-962, January 09-11, 2000, San Francisco, California, United States
	Daniel Reischert, Asymptotically fast computation of subresultants, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.233-240, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	Noam Nisan , Avi Wigderson, On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.723-732, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Manuel Bronstein , Thom Mulders , Jacques-Arthur Weil, On symmetric powers of differential operators, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.156-163, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	Stephen A. Cook, An overview of computational complexity, Communications of the ACM, v.26 n.6, p.400-408, June 1983
	E Kaltofen, Uniform closure properties of P-computable functions, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.330-337, May 28-30, 1986, Berkeley, California, United States
	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
	Erich Kaltofen , Wen-shin Lee , Austin A. Lobo, Early termination in Ben-Or/Tiwari sparse interpolation and a hybrid of Zippel's algorithm, Proceedings of the 2000 international symposium on Symbolic and algebraic computation, p.192-201, July 2000, St. Andrews, Scotland
	László Babai , Robert Beals , Jin-yi Cai , Gábor Ivanyos , Eugene M. Luks, Multiplicative equations over commuting matrices, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.498-507, January 28-30, 1996, Atlanta, Georgia, United States
	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
	Ming-Deh A. Huang , Ashwin J. Rao, A black box approach to the algebraic set decomposition problem, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.497-506, May 24-26, 1998, Dallas, Texas, United States
	Amos Beimel , Francesco Bergadano , Nader H. Bshouty , Eyal Kushilevitz , Stefano Varricchio, Learning functions represented as multiplicity automata, Journal of the ACM (JACM), v.47 n.3, p.506-530, May 2000
	Mark Giesbrecht, Fast algorithms for rational forms of integer matrices, Proceedings of the international symposium on Symbolic and algebraic computation, p.305-311, July 20-22, 1994, Oxford, United Kingdom
	J. Maurice Rojas, On the complexity of diophantine geometry in low dimensions (extended abstract), Proceedings of the thirty-first annual ACM symposium on Theory of computing, p.527-536, May 01-04, 1999, Atlanta, Georgia, United States
	John H. Reif, Work efficient parallel solution of Toeplitz systems and polynomial GCD, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.751-761, May 29-June 01, 1995, Las Vegas, Nevada, United States
	Rainer E. Burkard, Selected topics on assignment problems, Discrete Applied Mathematics, v.123 n.1-3, p.257-302, 15 November 2002
	Luis Miguel Pardo , Jorge San Martín, Deformation techniques to solve generalised Pham systems, Theoretical Computer Science, v.315 n.2-3, p.593-625, 6 May 2004
	Johannes Grabmeier , Erich Kaltofen , Volker Weispfenning, Cited References, Computer algebra handbook, Springer-Verlag New York, Inc., New York, NY, 2003
	Mark Giesbrecht , Erich Kaltofen , Wen-shin Lee, Algorithms for computing the sparsest shifts of polynomials via the Berlekamp/Massey algorithm, Proceedings of the 2002 international symposium on Symbolic and algebraic computation, p.101-108, July 07-10, 2002, Lille, France
	N. Bruno , J. Heintz , G. Matera , R. Wachenchauzer, Functional programming concepts and straight-line programs in computer algebra, Mathematics and Computers in Simulation, v.60 n.6, p.423-473, 15 October 2002
	Krishna V. Palem, Energy aware algorithm design via probabilistic computing: from algorithms and models to Moore's law and novel (semiconductor) devices, Proceedings of the 2003 international conference on Compilers, architecture and synthesis for embedded systems, p.113-116, October 30-November 01, 2003, San Jose, California, USA
	Wayne Eberly, Early termination over small fields, Proceedings of the 2003 international symposium on Symbolic and algebraic computation, p.80-87, August 03-06, 2003, Philadelphia, PA, USA
	Éric Schost, Complexity results for triangular sets, Journal of Symbolic Computation, v.36 n.3-4, p.555-594, September 2003
	Mark Giesbrecht , Erich Kaltofen , Wen-shin Lee, Algorithms for computing sparsest shifts of polynomials in power, Chebyshev, and Pochhammer bases, Journal of Symbolic Computation, v.36 n.3-4, p.401-424, September 2003
	G. Matera , A. Sedoglavic, Fast computation of discrete invariants associated to a differential rational mapping, Journal of Symbolic Computation, v.36 n.3-4, p.473-499, September 2003
	Erich Kaltofen , Wen-shin Lee, Early termination in sparse interpolation algorithms, Journal of Symbolic Computation, v.36 n.3-4, p.365-400, September 2003
	Sumit Gulwani , George C. Necula, Global value numbering using random interpretation, ACM SIGPLAN Notices, v.39 n.1, p.342-352, January 2004
	Carsten Damm , Markus Holzer , Pierre McKenzie, The complexity of tensor calculus, Computational Complexity, v.11 n.1/2, p.54-89, January 2003
	W. Eberly , M. Giesbrecht, Efficient decomposition of separable algebras, Journal of Symbolic Computation, v.37 n.1, p.35-81, January 2004
	Maurizio Bruglieri , Francesco Maffioli , Matthias Ehrgott, Cardinality constrained minimum cut problems: complexity and algorithms, Discrete Applied Mathematics, v.137 n.3, p.311-341, 15 March 2004
	Giovanni Gallo , Bhubaneswar Mishra, The complexity of resolvent resolved, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.280-289, January 23-25, 1994, Arlington, Virginia, United States
	Erich Kaltofen , Victor Pan, Processor efficient parallel solution of linear systems over an abstract field, Proceedings of the third annual ACM symposium on Parallel algorithms and architectures, p.180-191, July 21-24, 1991, Hilton Head, South Carolina, United States
	E. Kaltofen , M. Krishnamoorthy , B. D. Saunders, Fast parallel algorithms for similarity of matrices, Proceedings of the fifth ACM symposium on Symbolic and algebraic computation, p.65-70, July 21-23, 1986, Waterloo, Ontario, Canada
	Ioannis Emiris , John Canny, A practical method for the sparse resultant, Proceedings of the 1993 international symposium on Symbolic and algebraic computation, p.183-192, July 06-08, 1993, Kiev, Ukraine
	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
	Shuhong Gao, Factoring multivariate polynomials via partial differential equations, Mathematics of Computation, v.72 n.242, p.801-822, 1 April 2003
	A. Bompadre , G. Matera , R. Wachenchauzer , A. Waissbein, Polynomial equation solving by lifting procedures for ramified fibers, Theoretical Computer Science, v.315 n.2-3, p.335-369, 6 May 2004
	Dominique Michelucci , Jean-Michel Moreau, Lazy Arithmetic, IEEE Transactions on Computers, v.46 n.9, p.961-975, September 1997
	D. Gruntz , M. Monagan, Introduction to Gauss, ACM SIGSAM Bulletin, v.28 n.2, p.3-19, Aug. 1994
	Sumit Gulwani , George C. Necula, Discovering affine equalities using random interpretation, ACM SIGPLAN Notices, v.38 n.1, p.74-84, January 2003
	Krishna V. Palem, Energy Aware Computing through Probabilistic Switching: A Study of Limits, IEEE Transactions on Computers, v.54 n.9, p.1123-1137, September 2005
	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
	Piotr Sankowski, Processor efficient parallel matching, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA
	Arne Storjohann , Gilles Villard, Computing the rank and a small nullspace basis of a polynomial matrix, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.309-316, July 24-27, 2005, Beijing, China
	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
	Sebti Foufou , Dominique Michelucci , Jean-Paul Jurzak, Numerical decomposition of geometric constraints, Proceedings of the 2005 ACM symposium on Solid and physical modeling, p.143-151, June 13-15, 2005, Cambridge, Massachusetts
	John H. Reif, Efficient parallel factorization and solution of structured and unstructured linear systems, Journal of Computer and System Sciences, v.71 n.1, p.86-143, July 2005
	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
	Amihood Amir , Yonatan Aumann , Gary Benson , Avivit Levy , Ohad Lipsky , Ely Porat , Steven Skiena , Uzi Vishne, Pattern matching with address errors: rearrangement distances, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.1221-1229, January 22-26, 2006, Miami, Florida
	Jin-Yi Cai , Eric Bach, On testing for zero polynomials by a set of points with bounded precision, Theoretical Computer Science, v.296 n.1, p.15-25, 4 March 2003
	Lisi D'Alfonso , Gabriela Jeronimo , Pablo Solernó, On the complexity of the resolvent representation of some prime differential ideals, Journal of Complexity, v.22 n.3, p.396-430, June 2006
	Joseph (Yossi) Gil , Yoav Zibin, Randomised algorithms for isomorphisms of simple types, Mathematical Structures in Computer Science, v.17 n.3, p.565-584, June 2007
	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
	Christina Fragouli , Jörg Widmer , Jean-Yves Le Boudec, Efficient broadcasting using network coding, IEEE/ACM Transactions on Networking (TON), v.16 n.2, p.450-463, April 2008
	Timothy S. Freeman , Gregory M. Imirzian , Erich Kaltofen , Lakshman Yagati, Dagwood: a system for manipulating polynomials given by straight-line programs, ACM Transactions on Mathematical Software (TOMS), v.14 n.3, p.218-240, Sept. 1988
	R M Karp , E Upfal , A Wigderson, Constructing a perfect matching is in random NC, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.22-32, May 06-08, 1985, Providence, Rhode Island, United States
	William J. Turner, A block Wiedemann rank algorithm, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy
	Russell Impagliazzo, Can every randomized algorithm be derandomized?, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA
	Henrik Brosenne , Carsten Damm , Matthias Homeister , Stephan Waack, On approximation by ⊕-OBDDs, Information Processing Letters, v.102 n.1, p.17-21, April, 2007
	Clément Pernet , Arne Storjohann, Faster algorithms for the characteristic polynomial, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada
	Pascal Koiran , Sylvain Perifel, The complexity of two problems on arithmetic circuits, Theoretical Computer Science, v.389 n.1-2, p.172-181, December, 2007
	Christina Fragouli , Emina Soljanin, Network coding fundamentals, Foundations and Trends® in Networking, v.2 n.1, p.1-133, January 2007
	Erich Kaltofen , Zhengfeng Yang , Lihong Zhi, On probabilistic analysis of randomization in hybrid symbolic-numeric algorithms, Proceedings of the 2007 international workshop on Symbolic-numeric computation, July 25-27, 2007, London, Ontario, Canada
	Daniel Bleichenbacher , Aggelos Kiayias , Moti Yung, Decoding interleaved Reed-Solomon codes over noisy channels, Theoretical Computer Science, v.379 n.3, p.348-360, June, 2007
	Grégoire Lecerf, Improved dense multivariate polynomial factorization algorithms, Journal of Symbolic Computation, v.42 n.4, p.477-494, April, 2007
	Guillaume Chèze , Grégoire Lecerf, Lifting and recombination techniques for absolute factorization, Journal of Complexity, v.23 n.3, p.380-420, June, 2007
	Pierre Senellart , Serge Abiteboul, On the complexity of managing probabilistic XML data, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
	Aggelos Kiayias , Moti Yung, Cryptanalyzing the polynomial-reconstruction based public-key system under optimal parameter choice, Designs, Codes and Cryptography, v.43 n.2-3, p.61-78, June 2007
	Xavier Dahan , Xin Jin , Marc Moreno Maza , Éric Schost, Change of order for regular chains in positive dimension, Theoretical Computer Science, v.392 n.1-3, p.37-65, February, 2008
	A. Borodin , P. Tiwari, On the decidability of sparse univariate polynomial interpolation, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.535-545, May 13-17, 1990, Baltimore, Maryland, United States
	Y. N. Lakshman, On the complexity of computing a Gröbner basis for the radical of a zero dimensional ideal, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.555-563, May 13-17, 1990, Baltimore, Maryland, United States
	Erich Kaltofen , Zhengfeng Yang, On exact and approximate interpolation of sparse rational functions, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada
	Erich Kaltofen , Pascal Koiran, Expressing a fraction of two determinants as a determinant, Proceedings of the twenty-first international symposium on Symbolic and algebraic computation, July 20-23, 2008, Linz/Hagenberg, Austria
	Alin Bostan , Claude-Pierre Jeannerod , Éric Schost, Solving toeplitz- and vandermonde-like linear systems with large displacement rank, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada
	Seiji Isotani , Leônidas de Oliveira Brandão, An algorithm for automatic checking of exercises in a dynamic geometry system: iGeom, Computers & Education, v.51 n.3, p.1283-1303, November, 2008
	Wayne Eberly , Mark Giesbrecht , Pascal Giorgi , Arne Storjohann , Gilles Villard, Faster inversion and other black box matrix computations using efficient block projections, Proceedings of the 2007 international symposium on Symbolic and algebraic computation, July 29-August 01, 2007, Waterloo, Ontario, Canada
	Stephen A. Cook, An overview of computational complexity, ACM Turing award lectures, ACM, New York, NY, 2007
	Piotr Sankowski, Faster dynamic matchings and vertex connectivity, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.118-126, January 07-09, 2007, New Orleans, Louisiana
	V. Y. Pan , D. Grady , B. Murphy , G. Qian , R. E. Rosholt , A. D. Ruslanov, Schur aggregation for linear systems and determinants, Theoretical Computer Science, v.409 n.2, p.255-268, December, 2008
	Charles H. -P. Wen , Li-C. Wang , Kwang-Ting Cheng, Simulation-Based Functional Test Generation for Embedded Processors, IEEE Transactions on Computers, v.55 n.11, p.1335-1343, November 2006
	Alexandra Boldyreva , Craig Gentry , Adam O'Neill , Dae Hyun Yum, New Multiparty Signature Schemes for Network Routing Applications, ACM Transactions on Information and System Security (TISSEC), v.12 n.1, p.1-39, October 2008
	Alin Bostan , Claude-Pierre Jeannerod , Éric Schost, Solving structured linear systems with large displacement rank, Theoretical Computer Science, v.407 n.1-3, p.155-181, November, 2008
	Raphael Yuster, Efficient algorithms on sets of permutations, dominance, and real-weighted APSP, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.950-957, January 04-06, 2009, New York, New York
	Lingxiao Jiang , Zhendong Su, Automatic mining of functionally equivalent code fragments via random testing, Proceedings of the eighteenth international symposium on Software testing and analysis, July 19-23, 2009, Chicago, IL, USA
	Azaria Paz, Probabilistic algorithms, Encyclopedia of Computer Science, 4th edition, John Wiley and Sons Ltd., Chichester, 2003
	Neeraj Kayal , Nitin Saxena, Polynomial Identity Testing for Depth 3 Circuits, Computational Complexity, v.16 n.2, p.115-138, May 2007
	Amihood Amir , Yonatan Aumann , Gary Benson , Avivit Levy , Ohad Lipsky , Ely Porat , Steven Skiena , Uzi Vishne, Pattern matching with address errors: Rearrangement distances, Journal of Computer and System Sciences, v.75 n.6, p.359-370, September, 2009
	B. David Saunders , Bryan S. Youse, Large matrix, small rank, Proceedings of the 2009 international symposium on Symbolic and algebraic computation, July 28-31, 2009, Seoul, Republic of Korea