Читать книгу Hardness of Approximation Between P and NP - Aviad Rubinstein - Страница 6
ОглавлениеContents
| Preface | |
| Acknowledgments | |
| PART I | OVERVIEW |
| Chapter 1 | The Frontier of Intractability |
| 1.1 PPAD: Finding a Needle You Know Is in the Haystack | |
| 1.2 Quasi-Polynomial Time and the Birthday Paradox | |
| 1.3 Approximate Nash Equilibrium | |
| Chapter 2 | Preliminaries |
| Notation | |
| 2.1 Nash Equilibrium and Relaxations | |
| 2.2 PPAD and END-OF-A-LINE | |
| 2.3 Exponential Time Hypotheses | |
| 2.4 PCP Theorems | |
| 2.5 Learning Theory | |
| 2.6 Information Theory | |
| 2.7 Useful Lemmata | |
| 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) | |
| 12.2 Soundness | |
| Chapter 13 | Community Detection |
| 13.1 Related Works | |
| 13.2 Overview of Proofs | |
| 13.3 Hardness of Counting Communities | |
| 13.4 Hardness of Detecting Communities | |
| Chapter 14 | VC and Littlestone’s Dimensions |
| 14.1 Discussion | |
| 14.2 Techniques | |
| 14.3 Related Work | |
| 14.4 Inapproximability of the VC Dimension | |
| 14.5 Inapproximability of Littlestone’s Dimension | |
| 14.6 Quasi-polynomial Algorithm for Littlestone’s Dimension | |
| Chapter 15 | Signaling |
| 15.1 Techniques | |
| 15.2 Near-Optimal Signaling Is Hard | |
| PART V | APPROXIMATE NASH EQUILIBRIUM |
| Chapter 16 | 2-Player Approximate Nash Equilibrium |
| Additional Related Work | |
| 16.1 Technical Overview | |
| 16.2 END-OF-A-LINE with Local Computation | |
| 16.3 Holographic Proof | |
| 16.4 Polymatrix WeakNash | |
| 16.5 From Polymatrix to Bimatrix | |
| References | |
| Index | |
| Author Biography |
