next up previous
Next: Almost k-wise independence versus Up: Back at Weizmann (1998-2003) Previous: Locally Testable Codes and

Derandomization that is rarely wrong from short advice that is typically good

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



Oded Goldreich
2003-07-30