Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Probabilistic Computations:
TR96-055 | 22nd October 1996
Alexander E. Andreev, Andrea E. F. Clementi, Jose' D. P. Rolim

Hitting Properties of Hard Boolean Operators and their Consequences on BPP

Revisions: 1 , Comments: 1

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

ISSN 1433-8092 | Imprint