[+] PPAD (guest lecture by Constantinos Daskalakis). Economic games, Nash equilibrium, Nash's Theorem, Brouwer's FixedPoint Theorem, Sperner's Lemma, proofs and computational versions. Total search problems (TFNP), directed parity argument, End of the Line, PPAD, Arithmetic Circuit SAT.  [Scribe Notes] [src]  
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 PPADcomplete. Specifically, this lecture illustrates beautiful connections (reductions) between Nash's Theorem in economic game theory, Brouwer's FixedPoint Theorem in topology, and Sperner's Lemma in graph theory. These problems are all PPADcomplete, 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 PPADhardness (in the next lecture), we introduce an analog of Circuit SAT called Arithmetic Circuit SAT. 
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] 
The video above should play if your web browser supports either modern Flash or HTML5 video with H.264 or WebM codec. The handwritten notes and slides should advance automatically. If you have any trouble with playback, email Erik.