Theory

• Kolmogorov Complexity and Algorithmic Information Theory: The Deepest Measure of Information · 2025-07-30

  Dive into algorithmic information theory: Kolmogorov complexity as the ultimate measure of information content, its relationship to randomness (Martin-Löf tests), the incompressibility method for proving lower bounds, and the philosophical implications for science and mathematics.

• The PCP Theorem: Why Some Problems Are Hard Even to Approximate · 2025-03-30

  Unpack one of theoretical computer science's crown jewels: the PCP theorem, which shows that for many NP-hard problems, even finding an approximate solution is intractable — and how probabilistically checkable proofs revolutionized our understanding of hardness.

• The FLP Impossibility Result: Why Distributed Consensus Is Fundamentally Hard · 2025-01-15

  Explore the landmark Fischer-Lynch-Paterson result that proved no deterministic algorithm can achieve consensus in an asynchronous system with even one faulty process — and how the field evolved around this impossibility.

• Introduction to Automata Theory, Languages, and Computation (3rd ed.)
• Introduction to the Theory of Computation (3rd ed.)
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Principles of Database and Knowledge-Base Systems
• Structure and Interpretation of Computer Programs
• Structure and Interpretation of Computer Programs