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