This talk will give a history and philosophy of diagonalization as a tool to prove lower bounds in computational complexity. We will give several examples and discuss four possible approaches to using diagonalization to separate log-space from nondeterministic polynomial-time.

Host: Kim Skak Larsen