How to Cheat at “Who Wants to Be a Millionaire?” (and Show Non-Hardness of GapMCSP)
summary
Shows a concrete combinatorial scheme: split p pages into blocks of r/2, assign one friend to each pair-of-chapters construction (friend reads union of two blocks), and answer by unanimity-check combining over all friends who touched a block; with about O((p/r)^2) helpers this always outputs the correct multiple‑choice answer. Translates to complexity: unwind an NC0 reduction to view output bits as pages, use random restrictions to handle AC0, and derive unconditional non‑hardness results for GapMKTP/MKTP and a parity‑separation corollary.
AI-written summary · about
chapters (8)
- 0:00Introduction and motivation
- 1:16The game show model
- 4:02Defining the strategy
- 9:10Constructing the set family
- 12:43The combined algorithm
- 16:04Meta-complexity applications
- 18:04Proof sketch
- 20:34Closing and acknowledgments
related talks
33mWelfare Maximization with Limited Interaction: Information and Communication in Economics
58mMarkov Chain Mixing Times and Applications III
23mKarchmer-Wigderson Games for Hazard-free Computation
01h 17mInapproximability of Constraint Satisfaction Problems V
01h 22mTutorial 5: The GCT Chasm II
49mAn Introduction to Constraint Programming
01h 00mThe Classification Program for Counting Problems I
01h 25mInapproximability of Constraint Satisfaction Problems IV