6.890 Algorithmic Lower Bounds: Fun with Hardness Proofs (Fall '14)

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.