<div dir="ltr"><br><div class="gmail_quote"><div dir="ltr"><div id="m_7864688928021453644divtagdefaultwrapper" style="font-size:12pt;color:#000000;font-family:Calibri,Helvetica,sans-serif" dir="ltr">This Combinatorics seminar should be of interest to some of you.</div><div id="m_7864688928021453644divtagdefaultwrapper" style="font-size:12pt;color:#000000;font-family:Calibri,Helvetica,sans-serif" dir="ltr"><br></div><div id="m_7864688928021453644divtagdefaultwrapper" style="font-size:12pt;color:#000000;font-family:Calibri,Helvetica,sans-serif" dir="ltr">  --Dan</div><div id="m_7864688928021453644divtagdefaultwrapper" style="font-size:12pt;color:#000000;font-family:Calibri,Helvetica,sans-serif" dir="ltr"><br>
<p style="margin-top:0;margin-bottom:0"><br>
</p>
<p style="margin-top:0;margin-bottom:0"></p>
<div class="m_7864688928021453644field m_7864688928021453644field-name-field-speaker m_7864688928021453644field-type-text m_7864688928021453644field-label-inline m_7864688928021453644clearfix">
<div class="m_7864688928021453644field-item m_7864688928021453644even"><b>Speaker:</b>  Afonso Bandeira (Courant Institute - NYU)</div>
</div>
<div class="m_7864688928021453644field m_7864688928021453644field-name-body m_7864688928021453644field-type-text-with-summary m_7864688928021453644field-label-above">
<div class="m_7864688928021453644field-label"><b>Title:</b>  Optimizing and certifying bounds of random functions over the hypercube
<b><br>
</b></div>
<div class="m_7864688928021453644field-label"><b>Wednesday Feb 20 starting at 4pm in LOM 200</b>.<b><br>
</b></div><div class="m_7864688928021453644field-label"><br></div>
<div class="m_7864688928021453644field-label"><b>Abstract:</b> </div>
<div class="m_7864688928021453644field-items">
<div class="m_7864688928021453644field-item m_7864688928021453644even">
<div class="m_7864688928021453644tex2jax">
<p>We consider the problem of certifying an upper bound on the maximum value of a random quadratic form over the hypercube, which corresponds to the problem of optimizing the Hamiltonian of the Sherrington-Kirkpatrick model of statistical physics. We will show
 that, conditional on the “low-degree polynomials conjecture” concerning the computational hardness of random problems, there is no polynomial-time algorithm certifying a better upper bound than the largest eigenvalue of the coefficient matrix. If time permits
 we will discuss connections to optimization in random graphs.</p>
</div>
</div>
</div>
</div>
<br>
<p></p>
</div>
</div>

</div></div>