Previous slide Next slide Back to the first slide View text version


Notes:

Nisan major player with many important results in complexity theory.

Gives n^(log n) upper bound on universal traversal sequences.

Undirected connectivity in poly time and log2 n space also in log1.5 n space. This is work with Szemeredi and Wigderson.