Episode 82 · The Machine's Theorems
Speed Limits II: Hardness, Randomness and Quantum Oracles
Part 14 of "The Machine's Theorems". Farah and Augustin take on approximation hardness and semidefinite programming, Khot's Unique Games Conjecture ("a constraint puzzle where each clue fixes the neighbour exactly"), randomized logarithmic space, sensitivity versus block sensitivity after Hao Huang's 2019 breakthrough, parity and constant-depth quantum circuits, and the Aaronson–Kuperberg unitary synthesis problem. We read OpenAI's manuscripts in families 102 (Lean-listed, with a published reasoning summary), 103 (Lean-listed), 132 (Lean-listed), 274 (Lean-listed) and 283 (not Lean-listed), and Aaronson's reactions, including the story from his own household.
Listen to the show on your preferred podcast platform.
Inside this episode
- Cold open: "mommy, you got cooked"
- Hard to solve, hard to approximate
- The PCP theorem: proofs you can spot-check
- Unique Games: each clue fixes the neighbour exactly
- What a reduction actually is
- Testing a proof versus testing a theorem
- Why the conjecture mattered so much
- What family 102 claims
- Inside the proof: the completeness obstacle
- What the experts noticed
- Randomness and small memory: L equals RL equals BPL
- What family 103 claims
- Halfway: what we have so far
- Sensitivity and block sensitivity
- What family 132 claims
- A block sensitivity example you can say out loud
- How Huang's two-page proof worked
- Parity and shallow quantum circuits
- What family 274 claims
- Unitary synthesis: the opposite of what most expected
- What family 283 claims
- Oracles as lookup tables, and why constant error matters
- Why it matters to an engineer
- Closing: the brat and the theorem
Production credits & AI disclosure
Scripts generated with Claude Opus. Synthetic narration generated with Edge TTS. Reviewed, listened to, and approved by Sankalp Thakur.