Hardness of Approximation Between P and NP. Aviad Rubinstein
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 me1 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 (nlog(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].
•