Hardness of Approximation Between P and NP. Aviad Rubinstein

PART II COMMUNICATION COMPLEXITY Chapter 3 Communication Complexity of Approximate Nash Equilibrium Our Results 3.1 Uncoupled Dynamics 3.2 Techniques 3.3 Additional Related Literature 3.4 Proof Overview 3.5 Proofs 3.6 An Open Problem: Correlated Equilibria in 2-Player Games Chapter 4 Brouwer’s Fixed Point 4.1 BROUWER with ℓ∞ 4.2 Euclidean BROUWER PART III PPAD Chapter 5 PPAD-Hardness of Approximation Chapter 6 The Generalized Circuit Problem Our Results 6.1 Proof Overview 6.2 From Brouwer to ϵ-GCIRCUIT 6.3 GCIRCUIT with Fan-out 2 Chapter 7 Many-Player Games Related Works: Tractable Special Cases 7.1 Graphical, Polymatrix Games 7.2 Succinct Games Chapter 8 Bayesian Nash Equilibrium Chapter 9 Market Equilibrium 9.1 Why Are Non-Monotone Markets Hard? 9.2 High-Level Structure of the Proof 9.3 Adaptations for Constant Factor Inapproximability 9.4 Non-Monotone Markets: Proof of Inapproximability Chapter 10 CourseMatch 10.1 The Course Allocation Problem 10.2 A-CEEI Is PPAD-Hard 10.3 A-CEEI ∊ PPAD PART IV QUASI-POLYNOMIAL TIME Chapter 11 Birthday Repetition 11.1 Warm-Up: Best ϵ-Nash Chapter 12 Densest k-Subgraph 12.1 Construction (and Completeness)