6.5440 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall 2023)

This class is Costis Daskalakis's second of two guest lectures. We'll focus on examples of PPAD-completeness reductions, from Arithmetic Circuit SAT to Nash equilibria in a few different settings—ultimately two-player games. Not covered but in the slides are other examples of PPAD-hardness reductions.

Finally we'll hear about other classes related to PPAD, based on other styles of proofs of existence of solutions. PPA is based on the fact that, if a graph has a node of odd degree, then it must have another (which follows from the Handshaking Lemma). PLS is based on the fact that every directed acyclic graph has a sink node. PPP is based on the Pigeonhole Principle: any mapping from a set to a set of a smaller size has a collision.