[talks] Young Kun Ko will present his Generals April 29, 2015 at 2pm in CS 302

[Nicki Gotsis]

Young Kun Ko will present his Generals on April 29, 2015 at 2pm in CS 302. 

The members of his committee are: Mark Braverman (adviser), Zeev Dvir, and Elad Hazan 

Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. 

Abstract 
The celebrated PPAD hardness result for finding an exact Nash equilibrium in a two-player game 
initiated a quest for finding approximate Nash equilibria efficiently, and is one of the major open 
questions in algorithmic game theory. 
We study the computational complexity of finding an ε-approximate Nash equilibrium with 
good social welfare. Hazan and Krauthgamer and subsequent improvements showed that finding 
an ε-approximate Nash equilibrium with good social welfare in a two player game and many variants 
of this problem is at least as hard as finding a planted clique of size O(log n) in the random graph 
G(n, 1/2). 
We show that any polynomial time algorithm that finds an ε-approximate Nash equilibrium 
with good social welfare refutes (the worst-case) Exponential Time Hypothesis by Impagliazzo and 
Paturi, confirming the recent conjecture by Aaronson, Impagliazzo and Moshkovitz. Specifically, it 
would imply a 2O˜(n1/2) algorithm for SAT. 
Our lower bound matches the quasi-polynomial time algorithm by Lipton, Markakis and Mehta for solving the problem. 

Reading List 
Textbooks 
• Computational Complexity (Arora & Barak) 
Papers 
• How hard is it to approximate the best Nash Equilibrium? by Elad Hazan and Robert 
Krauthgamer 
• Inapproximability of NP-complete variants of Nash equilibrium by Per Austrin, Mark Braverman, 
Eden Chlamtac 
• Playing large games using simple strategies by Richard J. Lipton, Evangelos Markakis, and 
Aranyak Mehta 
• AM with multiple Merlins by Scott Aaronson, Russell Impagliazzo, and Dana Moshkovitz 
• Quantum de finetti theorems under local measurements with applications by Fernando G. S. 
L. Brandao and Aram Harrow 
• Interactive proofs and the hardness of approximating cliques by Uriel Feige, Shafi Goldwasser, 
Laszlo Lovasz, Shmuel Safra, and Mario Szegedy 
• Inapproximability of densest k-subgraph from average case hardness by Noga Alon, Sanjeev 
Arora, Rajsekar Manokaran, Dana Moshkovitz, and Omri Weinstein 
• Graph expansion and the unique games conjecture by Prasad Raghavendra and David Steurer 
• Finding endogenously formed communities by Maria-Florina Balcan, Christian Borgs, Mark 
Braverman, Jennifer Chayes, and Shang-Hua Teng 
• The PCP theorem by gap amplification by Irit Dinur 
_______________________________________________ 
talks mailing list 
talks at lists.cs.princeton.edu 
To edit subscription settings or remove yourself, use this link: 
https://lists.cs.princeton.edu/mailman/listinfo/talks