__
TR02-039 | 30th June 2002 00:00
__

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

**Abstract:**
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 ERH),

we present a {\em deterministic}\/ polynomial-time algorithm

that correctly decides primality

on all but at most $2^{{0.63}n}$ of the $n$-bit integers.

Using a plausible complexity assumption

(i.e., that $\P$ cannot be approximated by $\size(p)^\SAT$,

for every polynomial $p$)

we show that, for every $\epsilon>0$, each problem in $\BPP$ has

a {\em deterministic}\/ polynomial-time algorithm that errs

on at most $2^{n^\epsilon}$ of the $n$-bit long inputs.

(The complexity assumption that we use is not known to imply $\BPP=\P$.)

All results are obtained as special cases

of a general methodology that

explores which probabilistic algorithms can be derandomized by

generating their coin tosses {\em deterministically} from

the input itself. We show that this is possible (for all but extremely

few inputs) for

algorithms which take advice (in the usual Karp-Lipton sense), in

which the advice string is short, and most choices of the advice

string are good for the algorithm.

To get the applications above and others,

we show that algorithms with short and typically-good advice

strings do exist, unconditionally for $\SL$ and Primality Testing,

and under reasonable assumptions for $\BPP$ and $\AM$.

__
Comment #1 to TR02-039 | 31st July 2002 11:11
__
#### Deradomization that is rarely wrong from short advice that is typically good

**Abstract:**
There is an error in the results claimed for Primality Testing,

and we hereby retract all of them. We relied on our weak memory

regarding the analysis of the Miller-Rabin test.

Unfortunately, our memory was wrong.

All the other results of the paper are intact.

(That is, the above effects only Theorem 4 (of Sections 1.3.1 and 5).