Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > TESTING PRIMALITY:
Reports tagged with Testing Primality:
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$).