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 >>>