<div dir="ltr"><div class="gmail-m_-8782703434377045148gmail-m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-gE gmail-m_-8782703434377045148gmail-m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-iv gmail-m_-8782703434377045148gmail-m_4635199650404141437gmail-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_-8782703434377045148gmail-m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-:jk" class="gmail-m_-8782703434377045148gmail-m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-ii gmail-m_-8782703434377045148gmail-m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-gt gmail-m_-8782703434377045148gmail-m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-adP gmail-m_-8782703434377045148gmail-m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-adO" style="margin-bottom:0px;margin-left:0px;padding-bottom:5px"><div id="gmail-m_-8782703434377045148gmail-m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-:qr" class="gmail-m_-8782703434377045148gmail-m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-a3s gmail-m_-8782703434377045148gmail-m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-aXjCH gmail-m_-8782703434377045148gmail-m_4635199650404141437gmail-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_-8782703434377045148gmail-m_4635199650404141437gmail-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-m_-8782703434377045148gmail-m_4635199650404141437gmail-il">Young</span></span> <span class="gmail-m_-8782703434377045148gmail-m_4635199650404141437gmail-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-m_-8782703434377045148gmail-m_4635199650404141437gmail-il">Researcher</span></span> Seminar <span class="gmail-m_-8782703434377045148gmail-m_4635199650404141437gmail-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_-8782703434377045148gmail-m_4635199650404141437gmail-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-m_-8782703434377045148gmail-m_4635199650404141437gmail-il">researcher</span></span>.php</a>) features talks by Ph.D. students and postdocs whose <span class="gmail-m_-8782703434377045148gmail-m_4635199650404141437gmail-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-m_-8782703434377045148gmail-m_4635199650404141437gmail-il">research</span></span> is of broad interest to the computer science community. The <span class="gmail-m_-8782703434377045148gmail-m_4635199650404141437gmail-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_-8782703434377045148gmail-m_4635199650404141437gmail-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-m_-8782703434377045148gmail-m_4635199650404141437gmail-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></div></div><div class="gmail_extra"><br clear="all"><div><div class="gmail_signature" data-smartmail="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>
<br><div class="gmail_quote">On Tue, May 16, 2017 at 2:29 PM, Mary Marre <span dir="ltr"><<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="m_-8782703434377045148gmail-m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-gE m_-8782703434377045148gmail-m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-iv m_-8782703434377045148gmail-m_4635199650404141437gmail-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="m_-8782703434377045148gmail-m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-:jk" class="m_-8782703434377045148gmail-m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-ii m_-8782703434377045148gmail-m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-gt m_-8782703434377045148gmail-m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-adP m_-8782703434377045148gmail-m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-adO" style="margin-bottom:0px;margin-left:0px;padding-bottom:5px"><div id="m_-8782703434377045148gmail-m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-:qr" class="m_-8782703434377045148gmail-m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-a3s m_-8782703434377045148gmail-m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-aXjCH m_-8782703434377045148gmail-m_4635199650404141437gmail-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="m_-8782703434377045148gmail-m_4635199650404141437gmail-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="m_-8782703434377045148gmail-m_4635199650404141437gmail-il">Young</span></span> <span class="m_-8782703434377045148gmail-m_4635199650404141437gmail-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="m_-8782703434377045148gmail-m_4635199650404141437gmail-il">Researcher</span></span> Seminar <span class="m_-8782703434377045148gmail-m_4635199650404141437gmail-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="m_-8782703434377045148gmail-m_4635199650404141437gmail-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="m_-8782703434377045148gmail-m_4635199650404141437gmail-il">researcher</span></span>.php</a>) features talks by Ph.D. students and postdocs whose <span class="m_-8782703434377045148gmail-m_4635199650404141437gmail-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="m_-8782703434377045148gmail-m_4635199650404141437gmail-il">research</span></span> is of broad interest to the computer science community. The <span class="m_-8782703434377045148gmail-m_4635199650404141437gmail-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="m_-8782703434377045148gmail-m_4635199650404141437gmail-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="m_-8782703434377045148gmail-m_4635199650404141437gmail-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></div></div></div></div></div><div class="gmail_extra"><br clear="all"><div><div class="m_-8782703434377045148gmail_signature" data-smartmail="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:<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>
<br><div class="gmail_quote">On Wed, May 10, 2017 at 5:06 PM, Mary Marre <span dir="ltr"><<a href="mailto:mmarre@ttic.edu" target="_blank">mmarre@ttic.edu</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="m_-8782703434377045148m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-gE m_-8782703434377045148m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-iv m_-8782703434377045148m_4635199650404141437gmail-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="m_-8782703434377045148m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-:jk" class="m_-8782703434377045148m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-ii m_-8782703434377045148m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-gt m_-8782703434377045148m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-adP m_-8782703434377045148m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-adO" style="margin-bottom:0px;margin-left:0px;padding-bottom:5px"><div id="m_-8782703434377045148m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-:qr" class="m_-8782703434377045148m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-a3s m_-8782703434377045148m_4635199650404141437gmail-m_-8851913240295298494gmail-m_-2556873356046171619gmail-m_6077973053988611529gmail-m_5169817330970536202gmail-aXjCH m_-8782703434377045148m_4635199650404141437gmail-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="m_-8782703434377045148m_4635199650404141437gmail-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="m_-8782703434377045148m_4635199650404141437gmail-il">Young</span></span> <span class="m_-8782703434377045148m_4635199650404141437gmail-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="m_-8782703434377045148m_4635199650404141437gmail-il">Researcher</span></span> Seminar <span class="m_-8782703434377045148m_4635199650404141437gmail-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="m_-8782703434377045148m_4635199650404141437gmail-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="m_-8782703434377045148m_4635199650404141437gmail-il">researcher</span></span>.php</a>) features talks by Ph.D. students and postdocs whose <span class="m_-8782703434377045148m_4635199650404141437gmail-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="m_-8782703434377045148m_4635199650404141437gmail-il">research</span></span> is of broad interest to the computer science community. The <span class="m_-8782703434377045148m_4635199650404141437gmail-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="m_-8782703434377045148m_4635199650404141437gmail-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="m_-8782703434377045148m_4635199650404141437gmail-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="m_-8782703434377045148m_4635199650404141437gmail_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>
</blockquote></div><br></div></div>
</blockquote></div><br></div>