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

Oded Goldreich

The notion of promise problems was introduced and initially studied

by Even, Selman and Yacobi

(Information and Control, Vol.~61, pages 159-173, 1984).

In this article we survey some of the applications that this

notion has found in the twenty years that elapsed.

These include the notion ...
more >>>