Bpp has subexponential time simulations unless exptime has publishable proofs (extended abstract) (1993).

Content Provider	CiteSeerX
Author	Babai, László Nissan, Noam Fortnow, Lance Wigderson, Avi
Abstract	We show that BPP can be simulated in subexponential time for infinitely many input lengths unless exponential time ffl collapses to the second level of the polynomial-time hierarchy, ffl has polynomial-size circuits and ffl has publishable proofs (EXPTIME=MA). We also show that BPP is contained in subexponential time unless exponential time has publishable proofs for infinitely many input lengths. In addition, we show BPP can be simulated in subexponential time for infinitely many input lengths unless there exist unary languages in MA n P . The proofs are based on the recent characterization of the power of multiprover interactive protocols and on random self-reducibility via low degree polynomials. They exhibit an interplay between Boolean circuit simulation, interactive proofs and classical complexity classes. An important feature of this proof is that it does not ...
File Format	PDF
Publisher Date	1993-01-01
Access Restriction	Open
Subject Keyword	Publishable Proof Subexponential Time Subexponential Time Simulation Extended Abstract Polynomial-time Hierarchy Low Degree Polynomial Many Input Length Recent Characterization Important Feature Polynomial-size Circuit Interactive Proof Classical Complexity Class Exponential Time Second Level Multiprover Interactive Protocol Boolean Circuit Simulation Chicago Hebrew University Abstract Exponential Time Ffl Collapse Unary Language Exptime Ma
Content Type	Text