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 #2 to TR10-135 | 23rd December 2010 12:38

In a World of P=BPP

RSS-Feed




Revision #2
Authors: Oded Goldreich
Accepted on: 23rd December 2010 12:38
Downloads: 2038
Keywords: 


Abstract:

We show that proving results such as BPP=P essentially
necessitate the construction of suitable pseudorandom generators
(i.e., generators that suffice for such derandomization results).
In particular, the main incarnation of this equivalence
refers to the standard notion of uniform derandomization
and to the corresponding pseudorandom generators
(i.e., the standard uniform notion of ``canonical derandomizers'').
This equivalence bypasses the question of which hardness assumptions
are required for establishing such derandomization results,
which has received considerable attention in the last decade or so
(starting with Impagliazzo and Wigderson [JCSS, 2001]).

We also identify a natural class of search problems
that can be solved by deterministic polynomial-time
reductions to BPP. This result is instrumental to the
construction of the aforementioned pseudorandom generators
(based on the assumption BPP=P), which is actually a
reduction of the ``construction problem'' to BPP.

Caveat: Throughout the text, we abuse standard notation
by letting BPP, P etc denote classes of promise problems.



Changes to previous version:

Some (non-minor but non-major) corrections and additions; most importantly see the last paragraph of the proof of Thm 4.9.


Revision #1 to TR10-135 | 28th August 2010 10:56

In a World of P=BPP





Revision #1
Authors: Oded Goldreich
Accepted on: 28th August 2010 10:57
Downloads: 1739
Keywords: 


Abstract:

We show that proving results such as BPP=P essentially
necessitate the construction of suitable pseudorandom generators
(i.e., generators that suffice for such derandomization results).
In particular, the main incarnation of this equivalence
refers to the standard notion of uniform derandomization
and to the corresponding pseudorandom generators
(i.e., the standard uniform notion of ``canonical derandomizers'').
This equivalence bypasses the question of which hardness assumptions
are required for establishing such derandomization results,
which has received considerable attention in the last decade or so
(starting with Impagliazzo and Wigderson [JCSS, 2001]).

We also identify a natural class of search problems
that can be solved by deterministic polynomial-time
reductions to BPP. This result is instrumental to the
construction of the aforementioned pseudorandom generators
(based on the assumption BPP=P), which is actually a
reduction of the ``construction problem'' to BPP.

Caveat: Throughout the text, we abuse standard notation
by letting BPP, P etc denote classes of promise problems.



Changes to previous version:

correcting some typos, adding an observation re multiple samples (at the end of Sec 4.2).


Paper:

TR10-135 | 24th August 2010 15:48

In a World of P=BPP





TR10-135
Authors: Oded Goldreich
Publication: 24th August 2010 15:48
Downloads: 1729
Keywords: 


Abstract:

We show that proving results such as BPP=P essentially
necessitate the construction of suitable pseudorandom generators
(i.e., generators that suffice for such derandomization results).
In particular, the main incarnation of this equivalence
refers to the standard notion of uniform derandomization
and to the corresponding pseudorandom generators
(i.e., the standard uniform notion of ``canonical derandomizers'').
This equivalence bypasses the question of which hardness assumptions
are required for establishing such derandomization results,
which has received considerable attention in the last decade or so
(starting with Impagliazzo and Wigderson [JCSS, 2001]).

We also identify a natural class of search problems
that can be solved by deterministic polynomial-time
reductions to BPP. This result is instrumental to the
construction of the aforementioned pseudorandom generators
(based on the assumption BPP=P), which is actually a
reduction of the ``construction problem'' to BPP.

Caveat: Throughout the text, we abuse standard notation
by letting BPP, P etc denote classes of promise problems.



ISSN 1433-8092 | Imprint