Talk slides.
Samuel R. Buss.
"On the Power of Diagonalization for Separating Complexity Classes"
Yandex, Moscow, Russia.
July 21, 2015.
Download talk slides: PDF.
Abstract: We survey old and recent results about the use of diagonalization for separating complexity classes. Although many fundamental open problems, such as the P versus NP question, resist solution, diagonalization remains one of our best tools for the limited separations obtained to-date. The first such results were the time- and space-hiearchies obtained in the 1960's. Subsequent work by Cook, by Seiferas-Fischer-Meyer, by Zak, and recently by Fortnow and Santhanam have given strong hierarchies for non-deterministic time. Another line of work, arising from techniques of Nepomnjasci, Kannan, and Fortnow, uses an iterated form of diagonalization, called alternation-trading, to give lower bounds on space-bounded algorithms for Satisfiability. Williams used alternation-trading to show that Satisfiability cannot be computed in sublinear space in time n^c, for c =2 cos pi/7. In joint work with Williams, we have shown that c = 2 cos pi/7 is the optimal value which can be obtained with presently known methods.