Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR02-038 | 9th August 2002 00:00

Resource Tradeoffs and Derandomization

RSS-Feed




Revision #1
Authors: Rahul Santhanam
Accepted on: 9th August 2002 00:00
Downloads: 1217
Keywords: 


Abstract:

We consider uniform assumptions for derandomization. We provide intuitive evidence that BPP can be simulated non-trivially in deterministic time by showing that (1) There is a simulation of P in POLYLOGSPACE that is successful against all polynomial-time adversaries infinitely often, or BPP \subseteq SUBEXP (2) There is a simulation of P in SUBPSPACE that is successful against all subexponential-time adversaries infinitely often, or BPP \subseteq P. These results complement and extend earlier work of Sipser, Nisan-Wigderson and Lu.

We show similar tradeoffs between simulation of nondeterministic time by nondeterministic space and simulation of probabilistic time by nondeterministic time.

Finally, we give uniform assumptions under which the following results hold - (1)Probabilistic polynomial time has a strict hierarchy, (2) Probabilistic time can be simulated nontrivially by probabilistic space.


Paper:

TR02-038 | 5th June 2002 00:00

Resource Tradeoffs and Derandomization





TR02-038
Authors: Rahul Santhanam
Publication: 19th June 2002 18:00
Downloads: 1110
Keywords: 


Abstract:

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-
Wigderson and Lu.

We show similar tradeoffs between simulations of nondeterministic time
by nondeterministic space and simulations of randomized algorithms by
nondeterministic time. These results may be helpful in settling the
question of whether BPP=NEXP. We state two conjectures under which BPP
is not equal to NEXP: (1) An infinitely often (i.o.i.) version of
Lautemann's Theorem holds (2) Every language in BPP can be reduced to
SAT using nondeterministic reductions where the entire set of queries
can be computed in nondeterministic polynomial time from the input.
Unlike previous approaches, our approach does not seem to require
showing circuit lower bounds for NEXP.



ISSN 1433-8092 | Imprint