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 TR96-055 | 18th February 1997 00:00

Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs Revision of: TR96-055

RSS-Feed




Revision #1
Authors: Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim
Accepted on: 18th February 1997 00:00
Downloads: 3296
Keywords: 


Abstract:

We provide further results and a better description
of those in our earlier paper in TR96-055


Paper:

TR96-055 | 22nd October 1996 00:00

Hitting Properties of Hard Boolean Operators and their Consequences on BPP





TR96-055
Authors: Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim
Publication: 12th November 1996 15:56
Downloads: 1945
Keywords: 


Abstract:

We present the first worst-case hardness conditions
on the circuit complexity of EXP functions which are
sufficient to obtain P=BPP. In particular, we show that
from such hardness conditions it is possible to construct
quick Hitting Sets Generators with logarithmic prize.
As recently proved, i such generators
can efficiently derandomize any BPP-algorithm.


Comment(s):

Comment #1 to TR96-055 | 11th May 2001 12:34

Worst-case hardness suffices for derandomization: a new method for hardness-randomness trade-offs Comment on: TR96-055





Comment #1
Authors: Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim
Accepted on: 11th May 2001 12:34
Downloads: 1845
Keywords: 


Abstract:

We provide further results and a better description
of those in our earlier paper in TR96-055




ISSN 1433-8092 | Imprint