Linear gaps between degrees for the polynomial calculus modulo distinct primes

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Linear gaps between degrees for the polynomial calculus modulo distinct primes

Full text

Pdf (866 KB)

Source

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

Atlanta, Georgia, United States

Pages: 547 - 556

Year of Publication: 1999

ISBN:1-58113-067-8

Authors

Sam Buss	Department of Mathematics, Univ. of Calif., San Diego, La Jolla, CA
Dima Grigoriev	Computer Science and Engineering, Pennsylvania State University, University Park, PA
Russell Impagliazzo	Computer Science and Engineering, Univ. of Calif., San Diego, La Jolla, CA
Toniann Pitassi	Computer Science, University of Arizona, Tucson, AZ

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 9, Citation Count: 3

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/301250.301399 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	P. BEAME, R. IMPAGLIAZZO, J. KRAJICEK, T. PITASSI, AND P. PUDL,~K, Lower bounds on Hilbert's Nullstellensatz and propositional proofs, Proceedings of the London Mathematical Society, 73 (1996), pp. 1-26.
	2	S. R. Buss, Lower bounds on Nullsteltensatz proofs via designs, in Proof Complexity and Feasible Arithmetics, P. Beame and S. Buss, eds., American Mathematical Society, 1998, pp. 59-71.
	3	S. Buss , R. Impagliazzo , J. Krajíček , P. Pudlák , A. A. Razborov , J. Sgall, Proof complexity in algebraic systems and bounded depth Frege systems with modular counting, Computational Complexity, v.6 n.3, p.256-298, 1997 [doi>10.1007/BF01294258]
	4	Matthew Clegg , Jeffery Edmonds , Russell Impagliazzo, Using the Groebner basis algorithm to find proofs of unsatisfiability, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.174-183, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237860]
	5	D. GRIOORIEV, Nulistellensalz lower bounds for Tseitin tautologies. To appear, 39th Annual {EEE Syrup. on Foundations of Computer Science, 1998.
	6	J. KR^JfaEK, Lower bounds for a proof system with an exponential speed-up over constant depih Frege systems and over polynomial calculus. Typeset manuscript, 1997.
	7	~, On the degree of ideal membership proofs from uniform families of polynomials over a finite field. Typeset manuscript, 1998.
	8	T. PITASS;, Algebraic propositional proof systems, in Descriptive Complexity and Finite Models, N. Immerman and P. Kolaitis, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science ~31, American Mathematics Society, I996, pp. 215-244.
	9	A. A. R~^zBoaov, Lower bounds for lhe polynomial calculus. Typeset manuscript, 1996.
	10	R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.77-82, January 1987, New York, New York, United States [doi>10.1145/28395.28404]

CITED BY 3

	Eli Ben-Sasson, Hard examples for the bounded depth Frege proof system, Computational Complexity, v.11 n.3/4, p.109-136, March 2003
	Eli Ben-Sasson, Hard examples for bounded depth frege, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada
	Toniann Pitassi , Nathan Segerlind, Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.355-364, January 04-06, 2009, New York, New York