Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

Comments: 1

For every $\epsilon>0$,
we present a {\em deterministic}\/ log-space algorithm
that correctly decides undirected graph connectivity
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$).

Making no assumptions (and in particular not assuming the ... more >>>




ISSN 1433-8092 | Imprint