Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > AC0[2]:
Reports tagged with AC0[2]:
TR13-152 | 7th November 2013
Oded Goldreich, Avi Wigderson

#### On Derandomizing Algorithms that Err Extremely Rarely

Revisions: 2

{\em Does derandomization of probabilistic algorithms become easier when the number of bad'' random inputs is extremely small?}

In relation to the above question, we put forward the following {\em quantified derandomization challenge}:
For a class of circuits $\cal C$ (e.g., P/poly or $AC^0,AC^0[2]$) and a bounding function $B:\N\to\N$ (e.g., ... more >>>

ISSN 1433-8092 | Imprint