Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DIRECT PRODUCT PROBLEMS:
Reports tagged with Direct Product Problems:
TR02-039 | 30th June 2002
Oded Goldreich, Avi Wigderson

#### Derandomization that is rarely wrong from short advice that is typically good

For every $\epsilon>0$,
on all but at most $2^{n^\epsilon}$ of the $n$-vertex graphs.
The same holds for every problem in Symmetric Log-space (i.e., $\SL$).