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

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

Channel:
United States Simons Institute for the Theory of Computing
Subscribers:
68,800
Published on ● Video Link: https://www.youtube.com/watch?v=-DWmBhMgWrI


Duration: 12:49
5,516 views
210

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



Other Videos By Simons Institute for the Theory of Computing


2021-08-25Lower Bounds on Statistical Estimation Rates Under Various Constraints
2021-08-25On Algorithms and Barriers of Intractability in High-Dimensional Statistical Inference (continued)
2021-08-25On Algorithms and Barriers of Intractability in High-Dimensional Statistical Inference
2021-08-25Lower Bounds on Statistical Estimation Rates Under Various Constraints (continued)
2021-08-24Lower Bounds on Statistical Estimation Rates Under Various Constraints
2021-08-24The Fine Line between Hard and Easy Inference Problems: The View from CSPs (continued)
2021-08-24The Fine Line between Hard and Easy Inference Problems: The View from CSPs
2021-08-24In Search of New Algorithms Part II: Graphical Models
2021-08-23In Search of New Algorithms Part I: Neural Networks
2021-08-06An Almost Constant Lower Bound of the Isoperimetric Coefficient in the KLS Conjecture
2021-07-18Until the Sun Engulfs the Earth: Lower Bounds in Computational Complexity | Theory Shorts
2021-07-17Twisted Product Constructions for LDPC Quantum Codes
2021-07-17What the Foundations of Quantum Computer Science Teach Us About Chemistry
2021-07-17Electronic Structure in a Fixed Basis Is QMA-Complete
2021-07-17Improved Upper Bounds on the Stabilizer Rank of Magic States
2021-07-16Linear Growth of Quantum Circuit Complexity
2021-07-16Entanglement Spread in Communication Complexity and Many-Body Physics
2021-07-16Exponential Separations Between Learning With and Without Quantum Memory
2021-07-16A Rigorous and Robust Quantum Speed-up in Supervised Machine Learning
2021-07-16Provably Efficient Machine Learning for Quantum Many-Body Problems
2021-07-16Quantum Pseudorandomness and Classical Complexity


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing