Favorite Theorem 7

Favorite Theorem 7

• Nisan:
  • For any r(n) and s(n) there exists a pseudorandom generator that converts a random seed of length O(s(n) log r(n)) to r(n) bits that look random to any algorithm using s(n) space.
• Proof by recursively applying a special universal hash function.

Previous slide

Next slide

Back to the first slide

View Graphic Version

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.