<div dir="ltr"><div class="gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-gE gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-iv gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-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, May 17th at </span><span style="font-size:12.8px;font-family:arial,helvetica,sans-serif">11:00 am</span><br></div><div id="gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-:jk" class="gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-ii gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-gt gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-adP gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-adO" style="margin-bottom:0px;margin-left:0px;padding-bottom:5px"><div id="gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-:qr" class="gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-a3s gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-aXjCH gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-m157fdbb4a58e966d"><div dir="ltr"><div 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, Cornell</span></div><div><span style="font-family:arial,helvetica,sans-serif"><br></span></div><div><br></div><div>Title: Sample-Optimal Inference, the Method of Moments, and Community Detection.<br></div><div><blockquote type="cite" style="font-size:12.8px"></blockquote>Abstract: We propose a simple and efficient meta-algorithm for Bayesian estimation problems (i.e. hidden variable, latent variable, or planted problems). Our algorithm uses low-degree polynomials together with new and highly robust tensor decomposition methods. We focus on the question: for a given estimation problem, precisely how many samples (up to low-order additive terms) do polynomial-time algorithms require to obtain good estimates of hidden variables? Our meta-algorithm is broadly applicable, and achieves statistical or conjectured computational sample-complexity thresholds for many well-studied problems, including many for which previous algorithms were highly problem-specific.<br><blockquote type="cite" style="font-size:12.8px"></blockquote>As a running example we employ the stochastic block model -- a widely studied family of random graph models which contain latent community structure. We recover and unify the proofs of the best-known sample complexity bounds for the partial recovery problem in this model. We also give the first provable guarantees for partial recovery of community structure in constant-degree graphs where nodes may participate in many communities simultaneously. This model is known to exhibit a sharp sample complexity threshold -- with fewer than a very specific number of samples, recovering community structure becomes impossible. While previous explanations for this phenomenon appeal to sophisticated ideas from statistical mechanics, we give a new and simple explanation based on properties of low-degree polynomials.<br><blockquote type="cite" style="font-size:12.8px"></blockquote>Joint work with David Steurer</div><div><span style="font-family:arial,helvetica,sans-serif"><br></span></div><div><span style="font-family:arial,helvetica,sans-serif;font-size:12.8px"><br></span></div><div><span style="font-family:arial,helvetica,sans-serif;font-size:12.8px">Host: </span><span style="font-family:arial,helvetica,sans-serif"><a href="mailto:madhurt@ttic.edu" target="_blank">Madhur Tulsiani</a></span><br></div><div><span style="font-family:arial,helvetica,sans-serif"><br></span></div><div><div style="font-size:12.8px"><span style="font-family:arial,helvetica,sans-serif;font-size:12.8px">******************************<wbr>******************************<wbr>******************************<wbr>********</span><br></div><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_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-m_-6945911958741551355gmail-m_-1657390673076249714gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il"><span class="gmail-il">Young</span></span> <span class="gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-m_-6945911958741551355gmail-m_-1657390673076249714gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il"><span class="gmail-il">Researcher</span></span> Seminar <span class="gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-m_-6945911958741551355gmail-m_-1657390673076249714gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il"><wbr>Series</span> (<a href="http://www.ttic.edu/young-researcher.php" target="_blank">http://www.ttic.edu/yo<wbr>ung-<span class="gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-m_-6945911958741551355gmail-m_-1657390673076249714gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il"><span class="gmail-il">researcher</span></span>.php</a>) features talks by Ph.D. students and postdocs whose <span class="gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-m_-6945911958741551355gmail-m_-1657390673076249714gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il"><span class="gmail-il">research</span></span> is of broad interest to the computer science community. The <span class="gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-m_-6945911958741551355gmail-m_-1657390673076249714gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il">series</span> provides an opportunity for early-career <span class="gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-m_-6945911958741551355gmail-m_-1657390673076249714gmail-m_-3188658297228096346gmail-m_5767020761850768500gmail-m_9173063153275566578gmail-m_-8878884332252521502gmail-m_796811872599655286gmail-il"><span class="gmail-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><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></p><p class="MsoNormal" style="margin-bottom:0.0001pt;font-size:12.8px"><font face="arial, helvetica, sans-serif"><br></font></p></div></div></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>