A Commentary on the Collision of Worlds

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


Duration: 52:36
584 views
10

Rahul Santhanam (Oxford)
https://simons.berkeley.edu/talks/rahul-santhanam-oxford-2023-02-13
Lower Bounds, Learning, and Average-Case Complexity

I will celebrate Eric Allender's foundational work in meta-complexity
by examining his FSTTCS 2001 survey "When Worlds Collide: Derandomization,
Lower Bounds, and Kolmogorov Complexity" and describing how it anticipated and
influenced much of the recent work in the area.



Other Videos By Simons Institute for the Theory of Computing


2023-02-15Quantum Learning Algorithms Imply Circuit Lower Bounds
2023-02-15Range Avoidance, Remote Point, and Hard Partial Truth Table via Satisfying-Pairs Algorithms
2023-02-15Replicability in Learning
2023-02-15Extending Generalization Theory Towards Addressing Modern Challenges in Machine Learning
2023-02-14The Mystery of the Missing String
2023-02-14How to Cheat at “Who Wants to Be a Millionaire?” (and Show Non-Hardness of GapMCSP)
2023-02-14Journey with Eric Allender: From Turing Machines to Circuits, and Back
2023-02-14Improved Learning from Time-bounded Kolmogorov Complexity
2023-02-14NP-Hardness of Approximating Meta-Complexity: A Cryptographic Approach
2023-02-14Allender's Conjecture and its Impacts on Meta-Complexity
2023-02-13A Commentary on the Collision of Worlds
2023-02-09How Complex Is Complexity? Or What’s a ‘Meta’ for?
2023-02-02The Power of Randomness in Kolmogorov Complexity
2023-01-28Emulating Non-Local Games with Cryptography
2023-01-28Is Cryptography Feasible if P=NP?
2023-01-28Proof Complexity and TFNP
2023-01-28Learning versus Proofs of Complexity Lower Boundes
2023-01-27Understanding the Role of Derandomization in TCS
2023-01-27New Forms of Hardness versus Randomness
2023-01-27Quantum for Science
2023-01-27Adversarial Laws of Large Numbers and Optimal Regret in Online Classification


Tags:
Simons Institute
theoretical computer science
UC Berkeley
Computer Science
Theory of Computation
Theory of Computing
Lower Bounds Learning and Average-Case Complexity
Rahul Santhanam