Michael Sipser: Problems in the Theory of Computation

The Gradient: Perspectives on AI

In episode 119 of The Gradient Podcast, Daniel Bashir speaks to Professor Michael Sipser.

Professor Sipser is the Donner Professor of Mathematics and member of the Computer Science and Artificial Intelligence Laboratory at MIT.

He received his PhD from UC Berkeley in 1980 and joined the MIT faculty that same year. He was Chairman of Applied Mathematics from 1998 to 2000 and served as Head of the Mathematics Department 2004-2014. He served as interim Dean of Science 2013-2014 and then as Dean of Science 2014-2020.

He was a research staff member at IBM Research in 1980, spent the 1985-86 academic year on the faculty of the EECS department at Berkeley and at MSRI, and was a Lady Davis Fellow at Hebrew University in 1988. His research areas are in algorithms and complexity theory, specifically efficient error correcting codes, interactive proof systems, randomness, quantum computation, and establishing the inherent computational difficulty of problems. He is the author of the widely used textbook, Introduction to the Theory of Computation (Third Edition, Cengage, 2012).

Have suggestions for future podcast guests (or other feedback)? Let us know here or reach Daniel at [e-mail]

Subscribe to The Gradient Podcast: Apple Podcasts | Spotify | Pocket Casts | RSSFollow The Gradient on Twitter

Outline:

* (00:00) Intro

* (01:40) Professor Sipser’s background

* (04:35) On interesting questions

* (09:00) Different kinds of research problems

* (13:00) What makes certain problems difficult

* (18:48) Nature of the P vs NP problem

* (24:42) Identifying interesting problems

* (28:50) Lower bounds on the size of sweeping automata

* (29:50) Why sweeping automata + headway to P vs. NP

* (36:40) Insights from sweeping automata, infinite analogues to finite automata problems

* (40:45) Parity circuits

* (43:20) Probabilistic restriction method

* (47:20) Relativization and the polynomial time hierarchy

* (55:10) P vs. NP

* (57:23) The non-connection between GO’s polynomial space hardness and AlphaGo

* (1:00:40) On handicapping Turing Machines vs. oracle strategies

* (1:04:25) The Natural Proofs Barrier and approaches to P vs. NP

* (1:11:05) Debates on methods for P vs. NP

* (1:15:04) On the possibility of solving P vs. NP

* (1:18:20) On academia and its role

* (1:27:51) Outro

Links:

* Professor Sipser’s homepage

* Papers discussed/read

* Halting space-bounded computations (1978)

* Lower bounds on the size of sweeping automata (1979)

* GO is Polynomial-Space Hard (1980)

* A complexity theoretic approach to randomness (1983)

* Parity, circuits, and the polynomial-time hierarchy (1984)

* A follow-up to Furst-Saxe-Sipser

* The Complexity of Finite Functions (1991)

Get full access to The Gradient at thegradientpub.substack.com/subscribe