Oded Goldreich, Avi Wigderson

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

Omer Reingold

We present a deterministic, log-space algorithm that solves

st-connectivity in undirected graphs. The previous bound on the

space complexity of undirected st-connectivity was

log^{4/3}() obtained by Armoni, Ta-Shma, Wigderson and

Zhou. As undirected st-connectivity is

complete for the class of problems solvable by symmetric,

non-deterministic, log-space computations (the class SL), ...
more >>>

Oded Goldreich

We highlight a common theme in four relatively recent works

that establish remarkable results by an iterative approach.

Starting from a trivial construct,

each of these works applies an ingeniously designed

sequence of iterations that yields the desired result,

which is highly non-trivial. Furthermore, in each iteration,

more >>>