BPP has Subexponential Time Simulations unless EXPTIME has Publishable Proofs

Submitted by smcneil on Mon, 2012-01-16 00:00
Author: 
L . Babai
L. Fortnow
N. Nisan
A. Wigderson
Publication: 
Complexity Theory, vol. 3, pp. 307-318, 1993.
Proceedings of the 6th Structures in Complexity Theory Conference, pp. 213-19, July 1991.
Year: 
1991
Abstract: 
http://www.math.ias.edu/~avi/PUBLICATIONS/ABSTRACT/bfnw93.pdf
Hide Files
File: 
Journal version (pdf
Journal version (ps
bibTeX