Robert Robere. Proof Complexity: Algorithms and Lower Bounds
An introduction to modern proof complexity, emphasizing its connections with computational complexity and algorithms in optimization.
- from
- Theoretical Computer Science
- added
- 2026-10-10
- likes
- 0
similar
-
Demaine. Algorithmic Lower Bounds: Fun with Hardness Proofs ocw.mit.edu
A class taking a practical approach to proving problems can't be solved efficient.
-
Goldreich. Modern Cryptography, Probabilistic Proofs and Pseudorandomness wisdom.weizmann.ac.il
An introduction to the interwoven domains of cryptography, proofs and randomness.
-
Demaine, Gasarch & Hajiaghayi. Computers and Intractability: A Guide to Algorithmic Lower Bounds hardness.mit.edu
A sequel to Garey and Johnson's Computers and Intractability: A Guide to NP-Completeness. New topics include Parameterized Complexity, Lower bounds on approximation, Other hardness assumptions (ETH, 3SUM-conjecture, APSP-conjecture, UGC, Others), Online Algorithms, Streaming…
-
Rudich & Wigderson. Computational Complexity Theory ams.org
Three weeks of lectures from the IAS/Park City Mathematics Institute Summer School on computational complexity. Topics include reductions, lower-bounds, average-case complexity, randomness, interactive proof systems, probabilistically checkable proofs, quantum computing, and…
-
Papadimitriou. Computational Complexity pearson.com
Body of knowledge for studying the performance and limitations of computer algorithms. Among topics covered are: reductions and NP-completeness, cryptography and protocols, randomized algorithms, and approximability of optimization problems, circuit complexity, the structural…
-
Programs and Proofs ilyasergey.net
Book that gives a brief and practically-oriented introduction to interactive proofs in Coq which emphasizes the computational nature of inductive reasoning about decidable propositions via a small set of primitives from the SSReflect proof language.
Theoretical Computer Science › Computational Complexity > Proof Complexity > Lecture Notes: “An introduction to modern proof complexity, emphasizing its connections with computational complexity and algorithms in optimization.”