Hardness of approximation between P and NP

Contents......Page 10
Preface......Page 14
PART I. OVERVIEW......Page 18
1. The Frontier of Intractability......Page 20
2. Preliminaries......Page 36
PART II. COMMUNICATION COMPLEXITY......Page 48
3. Communication Complexity of Approximate Nash Equilibrium......Page 50
4. Brouwer’s Fixed Point......Page 78
PART III. PPAD......Page 94
5. PPAD-Hardness of Approximation......Page 96
6. The Generalized Circuit Problem......Page 100
7. Many-Player Games......Page 118
8. Bayesian Nash Equilibrium......Page 128
9. Market Equilibrium......Page 132
10. CourseMatch......Page 148
PART IV. QUASI-POLYNOMIAL TIME......Page 164
11. Birthday Repetition......Page 166
12. Densest k-Subgraph......Page 172
13. Community Detection......Page 194
14. VC and Littlestone’s Dimensions......Page 204
15. Signaling......Page 230
PART V. APPROXIMATE NASH EQUILIBRIUM......Page 238
16. 2-Player Approximate Nash Equilibrium......Page 240
References......Page 290
Index......Page 308
Author Biography......Page 320