<div dir="ltr"><div class="gmail_default" style=""><div class="gmail_default" style="font-size:small"><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;margin:0px"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b>    </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">  Monday, October 21st at 11:00 am</font></font><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b>     </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit">TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</font></font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>Who: </b>      Ruta Mehta, </font></font></font>University of Illinois at Urbana-Champaign</p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p></div><div class="gmail_default" style=""><p style="font-size:small"><font face="arial, sans-serif"><b>Title: </b>      </font>Sum-of-Squares Meets Nash: Lower Bounds for Finding Any Equilibrium</p><p style=""><font face="arial, sans-serif" style="font-size:small"><b>Abstract:</b> </font><font face="arial, sans-serif" style="">Computing Nash equilibrium (NE) in the
two-player game is a central question in algorithmic game theory. The main
motivation of this work is to understand the power of the sum-of-squares method
in computing equilibria, both exact and approximate.</font></p><span style="line-height:115%"><span style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif">We propose a framework of roundings for the sum-of-squares
algorithm (and convex relaxations in general) applicable to finding equilibria
in two-player bimatrix games. Specifically, we define the notion of oblivious
roundings with verification oracle (OV). These are algorithms that can access a
solution to the degree-d SoS relaxation to construct a list of candidate
(partial) solutions and invoke a verification oracle to check if a candidate in
the list gives an (exact or approximate) equilibrium.</font></span></span></div><div class="gmail_default" style=""><span style="line-height:115%"><font face="arial, sans-serif"><br><span style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial">This framework captures most known approximation algorithms
in combinatorial optimization including the celebrated semidefinite programming
based algorithms for Max-Cut, Constraint-Satisfaction Problems, and the recent
works on SoS relaxations for Unique Games/Small-Set Expansion, Best Separable
State, and </span><span style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial">many problems in unsupervised machine learning.</span></font></span></div><div class="gmail_default" style=""><span style="line-height:115%"><span style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><br></font></span></span></div><div class="gmail_default" style=""><span style="line-height:115%"><font face="arial, sans-serif" style=""><span style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial">Our main results are strong unconditional lower bounds in
this framework. Specifically, we show that for ε = Θ(1/poly(n)), there’s no
algorithm that uses a o(n)-degree SoS relaxation to construct a 2^o(n)-size
list of candidates and obtain an ε-approximate NE. For some constant ε, we show
a similar result for degree o(log (n)) SoS relaxation and list size no(log
(n)). Our results can be seen as an unconditional confirmation, in our
restricted algorithmic framework, of the recent Exponential Time Hypothesis for
PPAD.</span></font></span></div><div class="gmail_default" style=""><span style="line-height:115%"><font face="arial, sans-serif" style=""><br><span style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial">Our proof strategy involves constructing a family of games
that all share a common sum-of-squares solution but every (approximate)
equilibrium of any game is far from every equilibrium of any other game in the
family (in either player’s strategy). Along the way, we strengthen the
classical unconditional lower bound against enumerative algorithms for finding
approximate equilibria due to Daskalakis-Papadimitriou and the classical
hardness of computing equilibria due to Gilbow-Zemel.</span><br>
<br>
<span style="background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial">This is joint work with Pravesh Kothari.</span></font></span></div><div class="gmail_default" style=""><font face="Arial, sans-serif"><span style="font-size:12px"><br></span></font></div><div class="gmail_default" style=""><font face="Arial, sans-serif"><span style="font-size:12px"><br></span></font><div style="font-size:small"><div><div class="gmail_default"><div style="margin:0in 0in 0.0001pt"><div style="margin:0in 0in 0.0001pt">Host:<a href="mailto:mcallester@ttic.edu" target="_blank"> </a><a href="mailto:madhurt@ttic.edu">Madhur Tulsiani</a><br></div><div style="margin:0in 0in 0.0001pt"><br></div><div style="margin:0in 0in 0.0001pt"><br></div><div style="margin:0in 0in 0.0001pt"><br></div><div style="margin:0in 0in 0.0001pt"><br></div><div style="margin:0in 0in 0.0001pt"><br></div></div></div></div></div></div></div><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><div><div dir="ltr"><font face="arial, helvetica, sans-serif">Mary C. Marre</font><div><font face="arial, helvetica, sans-serif">Administrative Assistant</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">6045 S. Kenwood Avenue</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Room 517</font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i></div><div><i><font face="arial, helvetica, sans-serif">p:(773) 834-1757</font></i></div><div><i><font face="arial, helvetica, sans-serif">f: (773) 357-6970</font></i></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div></div></div></div></div></div></div></div></div></div>