How to Cheat at “Who Wants to Be a Millionaire?” (and Show Non-Hardness of GapMCSP)

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


Category:
Show
Duration: 23:25
321 views
3

Neekon Vafa (MIT)
https://simons.berkeley.edu/talks/how-cheat-who-wants-be-millionaire-show-non-hardness-gapmcsp
Lower Bounds, Learning, and Average-Case Complexity



Other Videos By Simons Institute for the Theory of Computing


2023-02-16New Lower Bounds and Derandomization for ACC, and a...
2023-02-16Learning Safe Action Models
2023-02-16Quantum Meets Minimum Circuit Size Problem
2023-02-16A Duality Between One-Way Functions and Average-Case Symmetry of Information
2023-02-15Learning Versus Pseudorandom Generators in Constant Parallel Time
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


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