Computational-Complexity

• 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.

• Algorithmic Game Theory: Nash Equilibrium Computation, PPAD-Completeness, and the Computational Lens on Strategy · 2019-11-23

  A rigorous look at algorithmic game theory—computing Nash equilibria, the PPAD complexity class, and how computational constraints reshape strategic reasoning.

• NP-Completeness: The Cook-Levin Theorem, Polynomial Reductions, and the Hardest Problems in NP · 2019-05-03

  A deep dive into the theory of NP-completeness—from Turing machines and the Cook-Levin theorem to the taxonomy of NP-complete problems and the P versus NP question.