Circuit Lower Bounds Collapse Relativized Complexity Classes

Atlanta, Georgia May 04-May 06

DOI Bookmark:

http://doi.ieeecomputersociety.org/10.1109/CCC.1999.766280

14th Annual IEEE Conference on Comput ...

	This Article
	PURCHASE ARTICLE: $19 PDF HTML IEEE Xplore Subscribers
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan/Endnote
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Richard Beigel Articles by Alexis Maciel

	ASCII Text	x
	Richard Beigel, Alexis Maciel, "Circuit Lower Bounds Collapse Relativized Complexity Classes," Computational Complexity, Annual IEEE Conference on, pp. 222, 14th Annual IEEE Conference on Computational Complexity (CoCo'99), 1999.

	BibTex	x
	@article{ 10.1109/CCC.1999.766280, author = {Richard Beigel and Alexis Maciel}, title = {Circuit Lower Bounds Collapse Relativized Complexity Classes}, journal ={Computational Complexity, Annual IEEE Conference on}, volume = {0}, year = {1999}, issn = {1093-0159}, pages = {222}, doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.1999.766280}, publisher = {IEEE Computer Society}, address = {Los Alamitos, CA, USA}, }

	RefWorks Procite/RefMan/Endnote	x
	TY - CONF JO - Computational Complexity, Annual IEEE Conference on TI - Circuit Lower Bounds Collapse Relativized Complexity Classes SN - 1093-0159 SP EP A1 - Richard Beigel, A1 - Alexis Maciel, PY - 1999 KW - complexity theory KW - relativized computation KW - oracles KW - Booleand circuits VL - 0 JA - Computational Complexity, Annual IEEE Conference on ER -

Richard Beigel, University of Illinois at Chicago

Alexis Maciel, Clarkson University

Since the publication of Furst, Saxe, and Sipser's seminal paper connecting AC0 with the polynomial hierarchy (Math. Systems Theory, 1984), it has been well known that circuit lower bounds allow you to construct oracles that separate complexity classes. We will show that similar circuit lower bounds allow you to construct oracles that collapse complexity classes. For example, based on Hastad's parity lower bound, we construct an oracle such that P = PH <> P = EXP.

Index Terms:

complexity theory, relativized computation, oracles, Booleand circuits

Citation:

Richard Beigel, Alexis Maciel, "Circuit Lower Bounds Collapse Relativized Complexity Classes," ccc, pp.222, 14th Annual IEEE Conference on Computational Complexity (CoCo'99), 1999

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.