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 23 Video     [previous] [next]

[+] OPTIONAL — PPAD (guest lecture by Constantinos Daskalakis). Economic games, Nash equilibrium, Nash's Theorem, Brouwer's Fixed-Point Theorem, Sperner's Lemma, proofs and computational versions. Total search problems (TFNP), directed parity argument, End of the Line, PPAD, Arithmetic Circuit SAT.

This lecture is the first of two guest lectures by Prof. Constantinos Daskalakis about the class PPAD which is intricately related to economic game theory (and a cool idea more generally). Costis is the expert in this area — his PhD thesis, for example, proved that finding Nash equilibria is PPAD-complete.

Specifically, this lecture illustrates beautiful connections (reductions) between Nash's Theorem in economic game theory, Brouwer's Fixed-Point Theorem in topology, and Sperner's Lemma in graph theory. These problems are all PPAD-complete, meaning that they are the hardest search problems that have guaranteed solutions via “directed parity arguments” (formally, a problem called End of the Line). To prove PPAD-hardness (in the next lecture), we introduce an analog of Circuit SAT called Arithmetic Circuit SAT.

Download Video: 360p, 720p

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

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

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

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