<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40"><head><META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=us-ascii"><meta name=Generator content="Microsoft Word 15 (filtered medium)"><style><!--
/* Font Definitions */
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Calibri;
panose-1:2 15 5 2 2 2 4 3 2 4;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:11.0pt;
font-family:"Calibri",sans-serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:#0563C1;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:#954F72;
text-decoration:underline;}
p
{mso-style-priority:99;
mso-margin-top-alt:auto;
margin-right:0in;
mso-margin-bottom-alt:auto;
margin-left:0in;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
pre
{mso-style-priority:99;
mso-style-link:"HTML Preformatted Char";
margin:0in;
margin-bottom:.0001pt;
font-size:10.0pt;
font-family:"Courier New";}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Calibri",sans-serif;
color:windowtext;}
span.HTMLPreformattedChar
{mso-style-name:"HTML Preformatted Char";
mso-style-priority:99;
mso-style-link:"HTML Preformatted";
font-family:"Courier New";}
.MsoChpDefault
{mso-style-type:export-only;
font-family:"Calibri",sans-serif;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]--></head><body lang=EN-US link="#0563C1" vlink="#954F72"><div class=WordSection1><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>INSTITUTE FOR ADVANCED STUDY<o:p></o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>School of Mathematics<o:p></o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>Princeton, NJ 08540<o:p></o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'><o:p> </o:p></span></pre><pre><b><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>Theoretical Computer Science/Discrete Math Seminars<o:p></o:p></span></b></pre><pre><b><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>Week of April 16, 2018<o:p></o:p></span></b></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'><o:p> </o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'><o:p> </o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>--------------<o:p></o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>To view mathematics in titles and abstracts, please click on the talk's link.<o:p></o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>--------------<o:p></o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'><o:p> </o:p></span></pre><pre><b><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>Monday, April 16<o:p></o:p></span></b></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'><o:p> </o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>Computer Science/Discrete Mathematics Seminar I<o:p></o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>Topic: Sums of Squares Over k-Subset Hypercubes<o:p></o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>Speaker: Annie Raymond, University of Massachusetts, Amherst<o:p></o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>Time/Room: 11:00am - 12:15pm/Simonyi Hall 101<o:p></o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>Abstract Link: <a href="http://www.math.ias.edu/seminars/abstract?event=128840">http://www.math.ias.edu/seminars/abstract?event=128840</a><o:p></o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'><o:p> </o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'><o:p> </o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'><o:p> </o:p></span></pre><pre><b><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>Tuesday, April 17<o:p></o:p></span></b></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'><o:p> </o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>Computer Science/Discrete Mathematics Seminar II<o:p></o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>Topic: A simple proof of a reverse Minkowski inequality<o:p></o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>Speaker: Noah Stephens-Davidowitz, Visitor, School of Mathematics<o:p></o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>Time/Room: 10:30am - 12:30pm/Simonyi Hall 101<o:p></o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>Abstract Link: <a href="http://www.math.ias.edu/seminars/abstract?event=136796">http://www.math.ias.edu/seminars/abstract?event=136796</a><o:p></o:p></span></pre><pre><span style='font-size:12.0pt;font-family:"Times New Roman",serif'><o:p> </o:p></span></pre><p class=MsoNormal style='margin-bottom:12.0pt'><span style='font-size:12.0pt;font-family:"Times New Roman",serif'><o:p> </o:p></span></p><p class=MsoNormal style='margin-bottom:12.0pt'><span style='font-size:12.0pt;font-family:"Times New Roman",serif'><o:p> </o:p></span></p><p class=MsoNormal style='margin-bottom:12.0pt'><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>1 Sums of Squares Over k-Subset Hypercubes <br> Annie Raymond <o:p></o:p></span></p><p>Polynomial optimization over hypercubes has important applications in combinatorial optimization. We develop a symmetry-reduction method that finds sums of squares certificates for non-negative symmetric polynomials over k-subset hypercubes that improves on a technique due to Gatermann and Parrilo. For every symmetric polynomial that has a sos expression of a fixed degree, our method finds a succinct sos expression whose size depends only on the degree and not on the number of variables. Our results relate naturally to Razborov's flag algebra calculus for solving problems in extremal combinatorics. This leads to new results involving flags and their power in finding sos certificates. This is joint work with James Saunderson, Mohit Singh and Rekha Thomas.<o:p></o:p></p><p class=MsoNormal style='margin-bottom:12.0pt'><span style='font-size:12.0pt;font-family:"Times New Roman",serif'><a href="http://www.math.ias.edu/seminars/abstract?event=128840">http://www.math.ias.edu/seminars/abstract?event=128840</a><br><br>2 A simple proof of a reverse Minkowski inequality <br> Noah Stephens-Davidowitz <o:p></o:p></span></p><p>We consider the following question: how many points with bounded norm can a "non-degenerate" lattice have. Here, by a "non-degenerate" lattice, we mean an n-dimensional lattice with no surprisingly dense lower-dimensional sublattices.<br> <br>Dadush and Regev conjectured an upper bound on this quantity (which they called a "reverse Minkowski-type inequality") and showed a number of applications---from cryptography to Brownian motion on flat tori. In joint work with Regev in 2016, we proved this conjecture via a rather tedious proof using two heavy hammers from convex geometry.<br> <br>Recently, Eldan showed how to remove the tedium from the proof, and even more recently, Dadush showed how to remove the heavy hammers (to prove a slightly different result). The resulting (still unpublished) streamlined proof is quite nice, and we present it more-or-less in full.<o:p></o:p></p><p class=MsoNormal><span style='font-size:12.0pt;font-family:"Times New Roman",serif'><a href="http://www.math.ias.edu/seminars/abstract?event=136796">http://www.math.ias.edu/seminars/abstract?event=136796</a><br><br><br><o:p></o:p></span></p><p class=MsoNormal><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>---------------------------------------<o:p></o:p></span></p><p class=MsoNormal><span style='font-size:12.0pt;font-family:"Times New Roman",serif'>Computer Science/Discrete Math Seminars can be found on our web page:<br><br><a href="http://www.math.ias.edu/csdm">http://www.math.ias.edu/csdm</a><br><a href="http://www.math.ias.edu/">http://www.math.ias.edu</a><o:p></o:p></span></p></div></body></html>