On ACC<supscrpt>0</supscrpt>[<italic>p<supscrpt>k</supscrpt></italic>] Frege proofs

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On ACC0[pk] Frege proofs

Full text

Pdf (1.56 MB)

Source

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

El Paso, Texas, United States

Pages: 720 - 729

Year of Publication: 1997

ISBN:0-89791-888-6

Authors

Alexis Maciel	Dept. of Computer Science and UMIACS, University of Maryland, College Park, MD
Toniann Pitassi	Department 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): 0, Downloads (12 Months): 10, Citation Count: 0

Additional Information:

references index terms collaborative colleagues peer to peer

Tools and Actions:	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/258533.258669 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.

	Aj1	M. Ajtai, "The complexity of the pigeonhole principle,'' forthcoming. Preliminary version, Proc. ~9th Annual IEEE FOGS, 346-355, 1988.
	Aj2	M. Ajtai, "Parity and the pigeonhole principle," In Feasible Mathematics, S.R. Buss and P.J. Scott, editors, 1-24. Birkhauser, 1990.
	AH	Eric Allender , Ulrich Hertrampf, Depth reduction for circuits of unbounded fan-in, Information and Computation, v.112 n.2, p.217-238, Aug 1 1994 [doi>10.1006/inco.1994.1057 ]
	Al	E. Allender, "A note on the power of threshold circuits," In Proc. 30th IEEE FOGS, 580-584, 1989.
	BC	S. Buss and P. Clote, "Cutting planes, connectivity, and threshold logic," Archive for Mathematical Logic, 35:1 (1996), 33-62.
	BIKPP	P. Beame, R. impagliazzo, J. Kraji~ek , T. Pitassi, and P. Pudl~k, "Lower bounds on Hilbert's Nullstellensatz and propositional proofs," Proc. of the London Math. Soc. To appear.
	BIKPRS	S. Buss, R. Impagliazzo, J. Krajf~ek, P. Pudlak, A. A. Razborov, and J. Sgall, "Proof complexity in algebraic systems and bounded-depth Frege systems with modular counting," Manuscript 1996.
	BPR	Maria Bonet , Toniann Pitassi , Ran Raz, Lower bounds for cutting planes proofs with small coefficients, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.575-584, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225275]
	BP	P. Beame, and T. Pitassi, "An exponential separation between the matching principle and the pigeonhole principle," To appear in Annals of Pure and Applied Logic.
	BT	Richard Beigel , Jun Tarui, On ACC, Computational Complexity, v.4 n.4, p.350-366, Oct. 1994 [doi>10.1007/BF01263423]
	CEI	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]
	GKRST	Frederic Green , Johannes Köbler , Kenneth W. Regan , Thomas Schwentick , Jacobo Torán, The power of the middle bit of a #P function, Journal of Computer and System Sciences, v.50 n.3, p.456-467, June 1995 [doi>10.1006/jcss.1995.1036 ]
	H	Haken, A. "The intractability of Resolution," Theoret. Comput. Sci., 39, 1985, 297-308.
	HC	Armin Haken , Stephen A. Cook, An exponential lower bound for the size of monotone real circuits, Journal of Computer and System Sciences, v.58 n.2, p.326-335, April 1999 [doi>10.1006/jcss.1998.1617 ]
	IP	Impagliazzo, R., and Pitassi, T., "Interpolation theorems for generalized Cutting Planes," Typeset manuscript, 1996.
	K1	Jan Krajíček, Bounded arithmetic, propositional logic, and complexity theory, Cambridge University Press, New York, NY, 1996
	K2	Krajff:ek J., "Interpolation theorems, lower bounds for proof systems and independence results for bounded arithmetic", to appear in the Journal of Symbolic Logic.
	Kraj	Krajff:ek J., "Discretely ordered modules as a first-order extension of the cutting planes system," Submitted.
	P1	Pudl~k , P. "Lower bounds for resolution and cutting planes proofs and monotone computation," Journal of Symbolic Logic, To appear.
	PS	Pudl~ik , P. and Sgall, J., "Algebraic models of computation and interpolation for algebraic proof systems," Manuscript, 1996.
	Ra1	A. Razborov, "Lower bounds for the size of circuits of bounded depth with basis { AND, PARITY }," Math. Notes of the A cad. of Sciences of the USSR, 41(4), a33-338, 1987.
	Ra2	A. Razborov, "Unprovability of lower bounds on the circuit size in certain fragments of bounded arithmetic," Izvestiya of the R.A.N., 59(1), 201-224.
	Ra3	A. Razborov, "Lower bounds for the polynomial calculus," Manuscript, November 1996.
	Re	K. Regan, "Efficient reductions from NP to Parity using Error-correcting codes," TR 93-24, Dept. of Computer Science, State University of New York, Buffalo, 1993.
	Ri	S. Riis, "Count(q) does not imply Count(p),' Manuscript 1995.
	Si	Michael Sipser, A complexity theoretic approach to randomness, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.330-335, December 1983 [doi>10.1145/800061.808762]
	Sm	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]
	W	Wigderson, A., "Lectures on the Fusion Method and Derandomization", Technical Report SOCS- 95.2, School of Computer Sci., McGill University, Montr6al, Qu6bec, Canada, 1994.
	Y	A. Yao, "On ACC and Threshold circuits," In Proc. 31st IEEE FOGS, 619-627, 1990.