ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > KEYWORD > EASY WITNESS METHOD:
Reports tagged with easy witness method:
TR02-038 | 5th June 2002
Rahul Santhanam

Resource Tradeoffs and Derandomization

Revisions: 1
We consider uniform assumptions for derandomization. We provide intuitive evidence that BPP can be simulated non-trivially in deterministic time by showing that (1) P \not \subseteq i.o.i.PLOYLOGSPACE implies BPP \subseteq SUBEXP (2) P \not \subseteq SUBPSPACE implies BPP = P. These results extend and complement earlier work of Sipser, Nisan- ... more >>>



ISSN 1433-8092 | Imprint