Demaine. Algorithmic Lower Bounds: Fun with Hardness Proofs
A class taking a practical approach to proving problems can't be solved efficient.
- from
- Theoretical Computer Science
- added
- 2026-10-10
- likes
- 0
similar
-
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…
-
Robert Robere. Proof Complexity: Algorithms and Lower Bounds cs.mcgill.ca
An introduction to modern proof complexity, emphasizing its connections with computational complexity and algorithms in optimization.
-
Demaine. Games, Puzzles, and Computation routledge.com
It shows that games and puzzles can serve as powerful models of computation, Offering a new way of thinking about computation.
-
Volume 3: Verified Functional Algorithms softwarefoundations.cis.upenn.edu
Demonstration of how a variety of fundamental data structures can be specified and verified.
-
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…
-
Demaine/Ku/Soloman. Introduction to Algorithms. MIT ocw.mit.edu
A first course on basic algorithms and data structures. — added by Erik himself!
Theoretical Computer Science › Lower Bounds > Lecture Videos Playlists: “A class taking a practical approach to proving problems can't be solved efficient.”