Title: Separating Small Complexity Classes
Speaker: Stephen Cook, Department of Computer Science, University of Toronto
The difficulty of proving the P not= NP conjecture is well-known, but the apparently simpler conjecture LogSpace not= NP is also wide open. A group of students, postdocs and faculty associated with the theory group here have been working for several years on separating LogSpace from P. We are a long way from a proof, but we do have interesting partial results.
Reference: "Pebbles and Branching Programs for Tree Evaluation", by Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman, Rahul Santhanam. ACM Trans. on Computation Theory, Vol. 3 No. 2, 2012.
Stephen Cook is University Professor Emeritus of Computer Science at the University of Toronto. He is the 1982 Turing Award Winner and the 2012 winner of the NSERC Gerhard Herzberg Canada Gold Medal for Science and Engineering. He has made extensive contributions to computational complexity, including his 1971 paper introducing the theory of NP Completeness. He is one of the founders of the field of propositional proof complexity. Cook is a Fellow of the American Academy of Arts and Science, the Royal Society of London, the Royal Society of Canada, and the ACM. He is a member of the National Academy of Sciences (USA). Thirty two students have completed their Ph.D. degrees under his supervision.
See event poster here
Contact info: email@example.com