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