Next: Almost k-wise independence versus
Up: Back at Weizmann (1998-2003)
Previous: Locally Testable Codes and
One result presented in this work is
a log-space deterministic algorithm that correctly
decides undirected connectivity on all but a sub-exponential
number of graphs of a certain size.
This and other results are obtained as special cases
of a general methodology that evolves around
short (and typically-good) advice strings.
Comments:
Authored by O. Goldreich and A. Wigderson. Appeared in
- Proceedings of RANDOM, Springer LNCS, Vol. 2483,
pages 209-223, 2002.
Oded Goldreich
2003-07-30