
Until the Sun Engulfs the Earth: Lower Bounds in Computational Complexity | Theory Shorts
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