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

Prof. Erik Demaine       TAs: Josh Brunner, Lily Chung, Jenny Diomidova


[Home] [Lectures] [Problem Sets] [Project] [Coauthor] [Accessibility]

Lecture 24 Video     [previous]

[+] OPTIONAL — PPAD Reductions (guest lecture by Constantinos Daskalakis). PPAD-completeness of Nash: graphical games, polymatrix games, 2-player games. PPA (Handshaking Lemma), PLS (sinks exist), PPP (pigeonhole principle).

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.

Download Video: 360p, 720p

Handwritten notes, page 1/6[previous page][next page][PDF]

Handwritten notes, page 1/6[previous page][next page][PDF]

Slides, page 1/42[previous page][next page][PDF]

Slides, page 1/42[previous page][next page][PDF]