<div dir="ltr"><div><br></div>I have been told that this seminar has been cancelled due to weather.<div>It will be rescheduled for later in the semester.</div><div><br></div><div> --Dan</div><div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Feb 18, 2019 at 9:29 PM Dan Spielman <<a href="mailto:daniel.spielman@yale.edu">daniel.spielman@yale.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><br><div class="gmail_quote"><div dir="ltr"><div id="gmail-m_244349996338611139m_7864688928021453644divtagdefaultwrapper" style="font-size:12pt;color:rgb(0,0,0);font-family:Calibri,Helvetica,sans-serif" dir="ltr">This Combinatorics seminar should be of interest to some of you.</div><div id="gmail-m_244349996338611139m_7864688928021453644divtagdefaultwrapper" style="font-size:12pt;color:rgb(0,0,0);font-family:Calibri,Helvetica,sans-serif" dir="ltr"><br></div><div id="gmail-m_244349996338611139m_7864688928021453644divtagdefaultwrapper" style="font-size:12pt;color:rgb(0,0,0);font-family:Calibri,Helvetica,sans-serif" dir="ltr"> --Dan</div><div id="gmail-m_244349996338611139m_7864688928021453644divtagdefaultwrapper" style="font-size:12pt;color:rgb(0,0,0);font-family:Calibri,Helvetica,sans-serif" dir="ltr"><br>
<p style="margin-top:0px;margin-bottom:0px"><br>
</p>
<p style="margin-top:0px;margin-bottom:0px"></p>
<div class="gmail-m_244349996338611139m_7864688928021453644field gmail-m_244349996338611139m_7864688928021453644field-name-field-speaker gmail-m_244349996338611139m_7864688928021453644field-type-text gmail-m_244349996338611139m_7864688928021453644field-label-inline gmail-m_244349996338611139m_7864688928021453644clearfix">
<div class="gmail-m_244349996338611139m_7864688928021453644field-item gmail-m_244349996338611139m_7864688928021453644even"><b>Speaker:</b> Afonso Bandeira (Courant Institute - NYU)</div>
</div>
<div class="gmail-m_244349996338611139m_7864688928021453644field gmail-m_244349996338611139m_7864688928021453644field-name-body gmail-m_244349996338611139m_7864688928021453644field-type-text-with-summary gmail-m_244349996338611139m_7864688928021453644field-label-above">
<div class="gmail-m_244349996338611139m_7864688928021453644field-label"><b>Title:</b> Optimizing and certifying bounds of random functions over the hypercube
<b><br>
</b></div>
<div class="gmail-m_244349996338611139m_7864688928021453644field-label"><b>Wednesday Feb 20 starting at 4pm in LOM 200</b>.<b><br>
</b></div><div class="gmail-m_244349996338611139m_7864688928021453644field-label"><br></div>
<div class="gmail-m_244349996338611139m_7864688928021453644field-label"><b>Abstract:</b> </div>
<div class="gmail-m_244349996338611139m_7864688928021453644field-items">
<div class="gmail-m_244349996338611139m_7864688928021453644field-item gmail-m_244349996338611139m_7864688928021453644even">
<div class="gmail-m_244349996338611139m_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>
</blockquote></div></div></div>