The independence of the modulo p counting principles

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The independence of the modulo p counting principles

Full text

Pdf (965 KB)

Source

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

Montreal, Quebec, Canada

Pages: 402 - 411

Year of Publication: 1994

ISBN:0-89791-663-8

Author

Miklos Ajtai

IBM Almaden Research Center

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 12, 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/195058.195207 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.

	Ajt1	M. Ajtai, The complexity of the Pigeonhole Principle 29-th, Annual Symposium on Foundations of Computer Science, 1988, 346-358. (Combinatorica, accepted for publication.)
	Ajt2	M. Ajtai, "Parity and the Pigeonhole Principle definability on finite structures," in Feasible Mathematics, Progress in Computer Science and Applied Logic, Vol. 9. Birkhauser, 1990. pp. 1-24
	Ajt3	M. Ajtai, The independence of the Modulo p Counting Principles. IBM Research Report, 1993.
	Ajt4	M. Ajtai, Symmetric Systems of Linear Equations Modulo p. IBM Research Report, 1993.
	Ajt5	M. Ajtai, On the Existence of Modulo p Cardinality Functions. IBM Research Report, 1993.
	BIKPPW	Paul Beame , Russell Impagliazzo , Jan Krajíček , Toniann Pitassi , Pavel Pudlák , Alan Woods, Exponential lower bounds for the pigeonhole principle, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.200-220, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129733]
	BP	P. Beame, T. Pitassi, An exponential Separation between the matching Principle and the Pigeonhole Principle.
	BPU	Stephen Bellantoni , Toniann Pitassi , Alasdair Urquhart, Approximation and small-depth Frege proofs, SIAM Journal on Computing, v.21 n.6, p.1161-1179, Dec. 1992 [doi>10.1137/0221068]
	CR	S. Cook and R. Rechkow# The relative efficiency of propositional proof systems, Journal of Symbolic Logic 44 (1977) (36-50).
	KPW	J.Krajicek, P.Pudlak, A. Woods. Exponential lower bounds to the size of bounded-depth Frege proofs of the pigeonhole principle. 1991.
	J	G. D. James "Representation Theory of the Symmetric Group". Springer Lecture Notes, 1972.
	PBI	T. Pitassi, P.Beame, R. Impagliazzo. Exponential lower bounds for the pigeonhole principle.

CITED BY 3

	Xudong Fu, Modular coloring formulas are hard for cutting planes proofs, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.595-602, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Russell Impagliazzo , Nathan Segerlind, Constant-depth Frege systems with counting axioms polynomially simulate Nullstellensatz refutations, ACM Transactions on Computational Logic (TOCL), v.7 n.2, p.199-218, April 2006
	Samuel R. Buss, Polynomial-size Frege and resolution proofs of st-connectivity and Hex tautologies, Theoretical Computer Science, v.357 n.1, p.35-52, 25 July 2006