<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><div class="gmail_default"><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"><p><font face="arial, sans-serif"><b>Title: </b> </font>Sum-of-Squares Meets Nash: Lower Bounds for Finding Any Equilibrium</p><p><font face="arial, sans-serif"><b>Abstract:</b> </font><font face="arial, sans-serif">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:14.95px"><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"><span style="line-height:14.95px"><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"><span style="line-height:14.95px"><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"><span style="line-height:14.95px"><font face="arial, sans-serif"><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"><span style="line-height:14.95px"><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">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"><font face="Arial, sans-serif"><span style="font-size:12px"><br></span></font></div><div class="gmail_default"><font face="Arial, sans-serif"><span style="font-size:12px"><br></span></font><div><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" target="_blank">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></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><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Tue, Oct 15, 2019 at 5:41 PM Mary Marre <<a href="mailto:mmarre@ttic.edu">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div 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><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><font face="arial, sans-serif" style="font-size:small"><b>Abstract:</b> </font><font face="arial, sans-serif">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><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><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><span style="line-height:115%"><font face="arial, sans-serif"><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><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">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><font face="Arial, sans-serif"><span style="font-size:12px"><br></span></font></div><div><font face="Arial, sans-serif"><span style="font-size:12px"><br></span></font><div style="font-size:small"><div><div><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" target="_blank">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"><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>
</blockquote></div></div>