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$.
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).
