Circuit Lower Bounds Collapse Relativized Complexity Classes

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	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

14th Annual IEEE Conference on Computational Complexity (CoCo'99)

Atlanta, Georgia

May 04-May 06

ISBN: 0-7695-0075-7

	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

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

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.