Читать книгу Hardness of Approximation Between P and NP - Aviad Rubinstein - Страница 7

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 an Approximate Competitive Equilibrium from Equal Incomes (A-CEEI). At the time, Abe was preparing for the launch of Course Match, a system that implements a heuristic algorithm for A-CEEI to assign students to courses at the Wharton School (University of Pennsylvania). Chapter 10, based on joint work with Abe and Christos, is devoted to the complexity of A-CEEI.

A-CEEI, like the rest of the problems in Part III, belongs to a special class (PPAD) of intractable problems that are total: their solution always exists, but it is hard to find it. Given our current understanding of computational complexity, this implies that they are unlikely to be NP-hard. In Part IV we move on to a different category of intractable problems: those that can be solved in quasi-polynomial (n^log(n)) time; this is typically prohibitively slow to implement even in moderate sized instances, but it is much faster than what we know or conjecture for problems like Satisfiability. This suggests that these problems are also not NP-hard. In both cases, proving intractability for problems that are not NP-hard requires both the right conditional assumptions (P ≠ PPAD and the “Exponential Time Hypothesis”), as well as special techniques.

The most difficult result in this book, for approximate Nash equilibrium (Part V), lies in the intersection of the PPAD problems from Part III and the quasi-polynomial time problems from Part IV. It combines ideas from both parts, together with new and old techniques from across theoretical computer science. It resolves an outstanding open problem that, as a student, I didn’t really mean to solve. Well … I’m glad I tried!

Acknowledgments

This book is based on my Ph.D. dissertation [Rubinstein 2017c], completed at University of California, Berkeley, with the wise advice of Christos Papadimitriou. My dissertation, in turn, was based on the following publications:

• “Inapproximability of VC Dimension and Littlestone’s Dimension” [Manurangsi and Rubinstein 2017].

• “Honest Signaling in Zero-Sum Games Is Hard, and Lying Is Even Harder” [Rubinstein 2017b].

• “Detecting Communities Is Hard (And Counting Them is Even Harder)” [Rubinstein 2017a].

• “ETH Hardness for Densest-k-Subgraph with Perfect Completeness” [Braverman et al. 2017].

• “Communication Complexity of Approximate Nash Equilibria” [Babichenko and Rubinstein 2017].

• “Settling the Complexity of Computing Approximate Two-Player Nash Equilibria” [Rubinstein 2016].

• “Inapproximability of Nash Equilibrium” [Rubinstein 2015].

• “The Complexity of Fairness Through Equilibrium” [Othman et al. 2016].

I am indebted to Christos and all my co-authors: Yakov Babichenko, Mark Braverman, Young Kun Ko, Pasin Manurangsi, Abraham Othman, and Omri Weinstein.

I am also grateful to Boaz Barak, Shai Ben-David, Jonah Brown-Cohen, Karthik C. S., Yang Cai, Alessandro Chiesa, Paul Christiano, Constantinos Daskalakis, Shaddin Dughmi, Mika Goos, Rishi Gupta, Elad Haramaty, Noam Nisan, Prasad Raghavendra, Tselil Schramm, Madhu Sudan, Luca Trevisan, Michael Viderman, and anonymous reviewers, for commenting on, correcting, and inspiring much of the content of this book.

The writing of this book was supported in part by the MSR Ph.D. Fellowship (and wonderful MSR summer internships).

This has been an amazing journey. I am most grateful for the opportunities I had to share it with my family and friends.

Aviad Rubinstein

Cambridge, MA

March 2019