Marginalia podcast

Complexity in Computer Science (Thomas Watson)

16.11.2026
0:00
50:35
Spol 15 sekunder tilbage
Spol 15 sekunder frem

Thomas Watson examines the capabilities and limits of efficient computation.

The discussion connects time and memory requirements with reductions, complexity classes, and P versus NP.

Randomness, hashing, error correction, and pseudorandomness reveal further ways to study computational resources.

The book extends these ideas to cryptography, learning, optimization, and verification.

Decision trees, communication protocols, and circuits provide concrete settings for understanding computational limits.

Corrections to the informal explanations: unbounded fan-in is finite for each circuit. BPP ⊆ P/poly follows from amplification and a union bound; the shifting argument concerns BPP ⊆ Σ₂P. PCP verification queries a specially encoded proof with bounded soundness error, rather than detecting almost any error from any three bits. The natural-proofs barrier assumes sufficiently strong pseudorandom functions; largeness means a non-negligible fraction of truth tables, and constructivity is measured in truth-table size. It does not rule out every approach to P versus NP. Amplification depends on the repetition count: 100 runs at error 1/3 do not ensure error below hardware-failure rates. Factoring concerns composite integers; randomly sampled strings can sometimes be compressible; heuristics may themselves use randomness. Path construction from reachability queries needs cycle avoidance.

Author: Thomas Watson

Source: Complexity in Computer Science · Thomas Watson

Series: AI & Computer Science · Book deep dive

Explore: AI & Computer Science

Related episodes: Backpropagation: Learning Representations by Back-Propagating Errors (Rumelhart, Hinton & Williams) · Yann LeCun & Randall Balestriero: The Platonic Representation Hypothesis with JEPAs

Got something to say to this podcast? Send a voicemail, and you might hear yourself on the next episode!

Flere episoder fra "Marginalia"