<div dir="ltr"><div class="gmail-m_3796957650158506323gmail-m_8121358918245704361gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-gE gmail-m_3796957650158506323gmail-m_8121358918245704361gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-iv gmail-m_3796957650158506323gmail-m_8121358918245704361gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-gt" style="font-size:12.8px;padding-left:0px"><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif"><b>CANCELLED DUE TO WEATHER!</b></span></div><div class="gmail-m_3796957650158506323gmail-m_8121358918245704361gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-gE gmail-m_3796957650158506323gmail-m_8121358918245704361gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-iv gmail-m_3796957650158506323gmail-m_8121358918245704361gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-gt" style="font-size:12.8px;padding-left:0px"><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif"><br></span></div><div class="gmail-m_3796957650158506323gmail-m_8121358918245704361gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-gE gmail-m_3796957650158506323gmail-m_8121358918245704361gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-iv gmail-m_3796957650158506323gmail-m_8121358918245704361gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-gt" style="font-size:12.8px;padding-left:0px"><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif">When:</span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif">     Wednesday, December 14th at </span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif">11:00 am</span><br></div><div id="gmail-m_3796957650158506323gmail-m_8121358918245704361gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-:jk" class="gmail-m_3796957650158506323gmail-m_8121358918245704361gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-ii gmail-m_3796957650158506323gmail-m_8121358918245704361gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-gt gmail-m_3796957650158506323gmail-m_8121358918245704361gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-adP gmail-m_3796957650158506323gmail-m_8121358918245704361gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-adO" style="font-size:12.8px;margin-bottom:0px;margin-left:0px;padding-bottom:5px"><div id="gmail-m_3796957650158506323gmail-m_8121358918245704361gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-:qr" class="gmail-m_3796957650158506323gmail-m_8121358918245704361gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-a3s gmail-m_3796957650158506323gmail-m_8121358918245704361gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-aXjCH gmail-m_3796957650158506323gmail-m_8121358918245704361gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-m157fdbb4a58e966d"><div dir="ltr" style="font-size:12.8px"><font face="arial, helvetica, sans-serif" style="font-size:12.8px"><span style="font-size:12.8px"><br></span><span style="font-size:12.8px">Where:    TTIC, 6045 S. Kenwood Avenue, 5th Floor, Room 526</span><span style="font-size:12.8px"><br><br></span><span style="font-size:12.8px">Who:   </span></font><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif">    Samuel Hopkins</span><span style="font-family:arial,helvetica,sans-serif">, Cornell</span></div><div dir="ltr" style="font-size:12.8px"><span style="font-family:arial,helvetica,sans-serif"><br></span></div><div dir="ltr" style="font-size:12.8px"><div style="font-size:12.8px">Title:        <span style="font-size:12.8px">A Nearly-Tight Sum-of-Squares Lower Bound for the Planted Clique Problem</span></div><div style="font-size:12.8px"><br></div><div style="font-size:12.8px"><span style="font-size:12.8px">Abstract:</span></div><div style="font-size:12.8px"><span style="font-size:12.8px">The Sum-of-Squares meta-algorithm has emerged as a powerful and unifying algorithm design technique for problems in numerous settings.</span></div><div style="font-size:12.8px"><span style="font-size:12.8px">In particular, much recent work has applied the Sum-of-Squares approach to obtain improved algorithms for average-case or planted problems.</span></div><div style="font-size:12.8px"><span style="font-size:12.8px">Some of these problems are members of the classic complexity theory zoo (e.g. random CSPs), while some are inspired by recent machine learning literature (e.g. random tensor decomposition).</span></div><div style="font-size:12.8px"><span style="font-size:12.8px">In this talk, we investigate the tantalizing possibility of using Sum-of-Squares to design an improved algorithm for the Planted Clique problem---the problem of recovering a large clique hidden in a random graph G(n,1/2).</span></div><div style="font-size:12.8px"><span style="font-size:12.8px">This problem, immune to every algorithmic attack made on it for 20 years, has become a key assumption in proving computational hardness of many statistical or average-case problems.</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">Ultimately, we show that Sum-of-Squares cannot give substantially improved algorithms for planted clique. </span></div><div style="font-size:12.8px"><span style="font-size:12.8px">Along the way, however, we will encounter strong evidence that Sum-of-Squares is a strictly stronger algorithm design technique for average-case problems than other powerful algorithmic frameworks, such as linear programming and spectral methods.</span></div><div style="font-size:12.8px"><span style="font-size:12.8px">We will emphasize a new technique, called pseudocalibration, to analyze Sum-of-Squares algorithms, which we believe will have broad applications to convex programming algorithms for statistical problems.</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">Based on joint work with Boaz Barak, Jon Kelner, Pravesh Kothari, Ankur Moitra, and Aaron Potechin</span></div><div><span style="font-size:12.8px"><br></span></div><div><span style="font-size:12.8px"><br></span></div></div><div style="font-size:12.8px"><span style="font-family:arial,helvetica,sans-serif">Host: <b><a href="mailto:madhurt@ttic.edu" target="_blank">Madhur Tulsiani</a></b></span></div><div style="font-size:12.8px"><span style="font-family:arial,helvetica,sans-serif"><br></span></div><div style="font-size:12.8px"><span style="font-family:arial,helvetica,sans-serif;font-size:12.8px">******************************</span><span style="font-family:arial,helvetica,sans-serif;font-size:12.8px"><wbr>******************************</span><span style="font-family:arial,helvetica,sans-serif;font-size:12.8px"><wbr>******************************</span><span style="font-family:arial,helvetica,sans-serif;font-size:12.8px"><wbr>********</span><br></div><div style="font-size:12.8px"><div style="font-size:12.8px"><div style="font-size:12.8px"><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px"><font face="arial, helvetica, sans-serif"> </font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px"><font face="arial, helvetica, sans-serif">The TTIC <span class="gmail-m_3796957650158506323gmail-m_1866167914836793064gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-m_-6945911958741551355gmail-m_-1657390673076249714gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il"><span class="gmail-m_3796957650158506323gmail-il">Young</span></span> <span class="gmail-m_3796957650158506323gmail-m_1866167914836793064gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-m_-6945911958741551355gmail-m_-1657390673076249714gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il"><span class="gmail-m_3796957650158506323gmail-il">Researcher</span></span> Seminar <span class="gmail-m_3796957650158506323gmail-m_1866167914836793064gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-m_-6945911958741551355gmail-m_-1657390673076249714gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il"><span class="gmail-m_3796957650158506323gmail-il"><wbr>Series</span></span> (<a href="http://www.ttic.edu/young-researcher.php" target="_blank">http://www.ttic.edu/yo<wbr>ung-<span class="gmail-m_3796957650158506323gmail-m_1866167914836793064gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-m_-6945911958741551355gmail-m_-1657390673076249714gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il"><span class="gmail-m_3796957650158506323gmail-il">researcher</span></span>.php</a>) features talks by Ph.D. students and postdocs whose <span class="gmail-m_3796957650158506323gmail-m_1866167914836793064gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-m_-6945911958741551355gmail-m_-1657390673076249714gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il"><span class="gmail-m_3796957650158506323gmail-il">research</span></span> is of broad interest to the computer science community. The <span class="gmail-m_3796957650158506323gmail-m_1866167914836793064gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-m_-6945911958741551355gmail-m_-1657390673076249714gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il"><span class="gmail-m_3796957650158506323gmail-il">series</span></span> provides an opportunity for early-career <span class="gmail-m_3796957650158506323gmail-m_1866167914836793064gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-m_-6945911958741551355gmail-m_-1657390673076249714gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il"><span class="gmail-m_3796957650158506323gmail-il">researchers</span></span> to present recent work to and meet with students and faculty at TTIC and nearby universities.</font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px"><font face="arial, helvetica, sans-serif"><br>The seminars are typically held on Wednesdays at 11:00am in TTIC Room 526.<br><br>For additional information, please contact Matthew Walter (<a href="mailto:mwalter@ttic.edu" target="_blank">mwalter@ttic.edu</a>).</font></p><div><font face="arial, helvetica, sans-serif"><br></font></div></div></div></div><div style="font-size:12.8px"><span style="font-family:arial,helvetica,sans-serif"><br></span></div><div style="font-size:12.8px"><span style="font-family:arial,helvetica,sans-serif"><br></span></div></div></div><div><div class="gmail_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:(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>