Hardness of Approximation Between P and NP. Aviad Rubinstein

Чтение книги онлайн.

СКАЧАТЬ 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

       Preface

      This book is based on my Ph.D. thesis (by the same title), which I wrote at the University of California, Berkeley, with the wise guidance of Christos Papadimitriou.

      In hindsight, it seems only natural that I ended up working on the complexity of Nash equilibrium, a problem that has been so closely associated with Christos for three decades. But the true story of how I came to work on equilibrium computation is completely different. During my first winter break at Berkeley, Abe Othman contacted me¹ and asked about the complexity of finding СКАЧАТЬ