The Gospel According to TCS
summary
Survey of core theoretical computer science claims that maps concrete tools to outcomes: polynomial-time reductions and NP-complete gadgets explain why disparate problems collapse to the same hardness; probabilistically checkable and interactive proofs plus analytic influence tools yield tight inapproximability like Håstad’s 7/8 barrier for 3‑SAT; the Unique Games Conjecture and Raghavendra’s result predict universal approximation algorithms; cryptographic completeness emerges from zero knowledge and oblivious transfer constructions; randomness extraction and hardness‑vs‑randomness derandomize BPP; proving strong lower bounds still fails (natural proofs barrier).
AI-written summary · about
chapters (12)
- 0:00Start
- 6:45Birth of TCS [Turing 1936]: "On computable numbers, with an application to the entscheidungsproblem"
- 7:38Technology Computer Revolution
- 10:51Easy and Hard Problems asymptotic complexity of functions
- 24:17The mystery of approximation
- 33:39Complexity-based Cryptography
- 35:35Secret communication Diffie-Hellman, Merkle 76 Public-key encryption Rivest-Shamir-Adleman 77
- 39:56Eliminating bad guys
- 41:25Oblivious computation with secret inputs 9(inputs)
- 42:47Secret communication is universal
- 50:02Introspection - why we fail - To prove general lower bounds, e.g. PNP
- 53:40TCS education challenges
related talks
29mAssumptions in cryptography and complexity theory
53mA Commentary on the Collision of Worlds
01h 22mTutorial 5: The GCT Chasm II
37mJourney with Eric Allender: From Turing Machines to Circuits, and Back
01h 25mInapproximability of Constraint Satisfaction Problems IV
54mConstraints, Gadgets, and Invariants
01h 04mFrontiers of Proof Complexity Lower Bounds via Algebraic Complexity & Open Problems
47mNatural Proofs in Algebraic Circuit Complexity