in the 14th Annual Conference on Computational Complexity, pp. 222-226, 1999
Authors: Richard Beigel and Alexis Maciel
Abstract: Since the publication of Furst, Saxe, and Sipser's seminal paper connecting AC0 with the polynomial hierarchy, 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 ⊂ PARITYP = EXP.