<div dir="ltr"><div class="gmail_default" style="font-size:12.8px"><font face="tahoma, sans-serif" color="#000000">When:     Thursday, January 26th at 11:00 am </font></div><div class="gmail_default" style="font-size:12.8px"><font face="tahoma, sans-serif" color="#000000"><br></font></div><div class="gmail_default" style="font-size:12.8px"><font face="tahoma, sans-serif" color="#000000">Where:    <span class="m_9067904842688472155gmail-m_3071693547520408192gmail-il">TTIC</span>, 6045 S Kenwood Avenue, 5th Floor, Room 526</font></div><div class="gmail_default" style="font-size:12.8px"><font face="tahoma, sans-serif" color="#000000"><br></font></div><div style="font-size:12.8px"><span style="font-size:12.8px"><font color="#000000">Who:       Tselil Schramm, UC Berkeley</font></span></div><div style="font-size:12.8px"><span style="font-size:12.8px"><font color="#000000"><br></font></span></div><div style="font-size:12.8px"><span style="font-size:12.8px"><font color="#000000"><br></font></span></div><div style="font-size:12.8px"><font color="#000000"><span style="font-size:12.8px">Title:        Adventures with Sum-of-Squares</span><br style="font-size:12.8px"><br style="font-size:12.8px"><span class="m_9067904842688472155gmail-m_-6371806173365686078gmail-m_4811989586900450008gmail-il" style="font-size:12.8px">Abstract</span><span style="font-size:12.8px">: The sum-of-squares hierarchy is a family of semidefinite programs that can capture any combinatorial optimization problem, allowing one to trade runtime for accuracy. The class of problems that sum-of-squares can solve efficiently is still not well-characterized---recently this has been a topic of intensive study in the theoretical computer science community, as the hierarchy has the potential to resolve long-standing open problems in the theory of approximation algorithms. In this talk, I will describe my own efforts towards characterizing the sum-of-squares hierarchy, through the lens of average-case problems. I'll talk about sum-of-squares algorithms for refuting random constraint satisfaction problems, about sum-of-squares lower bounds for planted clique and other average-case problems, and about using sum-of-squares algorithms to obtain fast spectral algorithms.</span><br style="font-size:12.8px"></font></div><div style="font-size:12.8px"><span style="font-size:12.8px"><font color="#000000"><br></font></span></div><div style="font-size:12.8px"><span style="font-size:12.8px"><font color="#000000"><br></font></span></div><div style="font-size:12.8px"><span style="font-size:12.8px"><font color="#000000">Host:</font></span><span style="color:rgb(80,0,80);font-size:12.8px"> <a href="mailto:yury@ttic.edu" target="_blank">Yury Makarychev</a></span></div><div style="font-size:12.8px"><span style="font-size:12.8px"><br></span></div><div style="font-size:12.8px"><span style="font-size:12.8px"><br></span></div><div style="font-size:12.8px"><span style="font-size:12.8px"><br></span></div><div style="font-size:12.8px"><span style="font-size:12.8px"><br></span></div><div><div class="m_9067904842688472155gmail_signature"><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 504</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:<a href="tel:(773)%20834-1757" value="+17738341757" target="_blank">(773) 834-1757</a></font></i></div><div><i><font face="arial, helvetica, sans-serif">f: <a href="tel:(773)%20357-6970" value="+17733576970" target="_blank">(773) 357-6970</a></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>