Until the Sun Engulfs Earth: Unlocking the Secrets of Computational Complexity 🌍

Theory Shorts is a documentary web series that explores topics from the Simons Institute’s research programs.

The second short film in the series, “Until the Sun Engulfs the Earth: Lower Bounds in Computational Complexity,” explores how we know that a problem is impossible to solve.

FURTHER READING
Fruit game optimal algorithm: Hossein Jowhari, Mert Saglam, Gábor Tardos. "Tight bounds for Lp
samplers, finding duplicates in streams, and related problems." PODS 2011: 49-58.

Fruit game optimal lower bound: Michael Kapralov, Jelani Nelson, Jakub Pachocki, Zhengyu Wang, David P. Woodruff, Mobin Yahyazadeh. "Optimal Lower Bounds for Universal Relation, and for Samplers and Finding Duplicates in Streams." FOCS 2017: 475-486.

FEATURING
Paul Beame
Faith Ellen
Jelani Nelson
Manuel Sabin
Madhu Sudan

DIRECTORS
Anil Ananthaswamy
Kristin Kane

SCIENTIFIC ADVISOR
Shafi Goldwasser

HOST/WRITER
Anil Ananthaswamy

EDITOR/PRODUCER
Kristin Kane

GRAPHIC AND ANIMATION DESIGNER
Barry Bödeker

ANIMATORS
Caresse Haaser
Kristin Kane

VIDEOGRAPHER
Drew Mason

PRODUCTION ASSISTANTS
Kevin Hung
Bexia Shi

COPY EDITOR
Preeti Aroon

TECH SUPPORT
Adriel Olmos

SPECIAL THANKS
Ryan Adams
Wesley Adams
Marco Carmosino
Kani Ilangovan
Sampath Kannan
Richard Karp
David Kim
Bryan Nelson
Jeremy Perlman
Kat Quigley
Siobhan Roberts
Amelia Saul
Umesh Vazirani

MUSIC
Dill Pickles (Heftone Banjo Orchestra)
Flamenco Rhythm (Sunsearcher)
Place Pigalle (Uncle Skeleton)
Plastic (Purple Moons)

SOUND EFFECTS
Courtesy of byxorna, inspectorj, janbezouska, jorickhoofd, kash15, kyster, robinhood76, smotasmr, svarvarn, and vandrandepinnen via Freesound.org

OTHER MEDIA
Becoming (Jan van IJken)
A Decade of Sun (Solar Dynamics Observatory, NASA)
Move Mountain (Kirsten Lepore)

© Simons Institute for the Theory of Computing, 2021