Rahul Santhanam

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 ...
more >>>

Gonen Krak, Noam Parzanchevski, Amnon Ta-Shma

We unconditionally prove there exists a promise problem in promise ZSUBEXP that cannot be solved in promise RP.

The proof technique builds upon Kabanets' easy witness method [Kab01] as implemented by Impagliazzo et. al [IKW02], with a separate diagonalization carried out on each of the two alternatives in the ...
more >>>