Until the Sun Engulfs the Earth: Lower Bounds in Computational Complexity | Theory Shorts
Вставка
- Опубліковано 17 лип 2021
- 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
Love the sounds! Delightfully crunchy! : )
Awesome video, of course, too!
Thanks for noticing!
Long time no see, Dr. Rojas!!! Hope you're still running REUs :)
@@sheridangrant4407 Actually, I just finished one a few weeks ago! : ) Hope you're doing well out there. Keep in touch! : )
Intriguing video presentation.. comments by the speakers connected ideas via quickly understandable examples and practical scenarios. Well done!
Very cool! I think many people who are interested in this would find it useful to have a list of sources for the claims that are mentioned. It would be great if someone could add these below the other sources which are already there.
Thank you, Csaba! I will check in with Jelani, Paul and Madhu for the specific papers referenced in their sections, and will add that to the page notes. Take care, Kristin
HELLO POTENTIAL VIEWERS: this video has claymation in it for some reason and its hilarious
Can't wait to learn more!
Merci!
++++