Tuesday, August 17th, 2021

Until the Sun Engulfs the Earth: Lower Bounds in Computational Complexity | Theory Shorts

As part of the Simons Institute's effort to foster public understanding of algorithmic science, we are delighted to share the second film in our documentary web series, Theory Shorts.

Until the Sun Engulfs the Earth: Lower Bounds in Computational Complexity explores how we know that a problem is impossible to solve.

Featuring Paul Beame (University of Washington), Faith Ellen (University of Toronto), Jelani Nelson (UC Berkeley), Manuel Sabin (UC Berkeley), and Madhu Sudan (Harvard University).

Directed by Anil Ananthaswamy and Kristin Kane.