<div dir="ltr"><div dir="ltr"><div><div class="gmail_default"><b style="font-size:small;font-family:arial,sans-serif">When</b><span style="font-family:arial,sans-serif">:     Monday, August 18<font size="1">th</font></span><span style="font-size:small;font-family:arial,sans-serif"> </span><span style="font-size:small;font-family:arial,sans-serif">from</span><b style="font-size:small;font-family:arial,sans-serif"> <span style="background-color:rgb(255,255,0)">9:30 - 10:30</span></b><b style="font-size:small;font-family:arial,sans-serif;background-color:rgb(255,255,0)">am CT</b></div><div><div class="gmail_default"><div class="gmail_default"><div><b><font face="arial, sans-serif"><br></font></b></div><div><b style="font-family:arial,sans-serif">Virtually</b><span style="font-family:arial,sans-serif">: via </span><a href="https://uchicago.zoom.us/j/96150477778?pwd=xZuTIgvLuS5uqTDjhHgFnJztmfaPNg.1" style="font-family:arial,sans-serif" target="_blank"><b>Zoom</b></a><span style="font-family:arial,sans-serif"> </span></div><div><font face="arial, sans-serif">                 </font></div><div><font face="arial, sans-serif"><b>Who:  </b>    </font>Mrinalkanti Ghosh, TTIC</div><div><font face="arial, sans-serif"><br></font></div></div><div class="gmail_default"><div style="border-top:none;border-right:none;border-left:none;border-bottom:2.25pt solid rgb(11,118,159);padding:0in 0in 1pt"></div><div><font face="arial, sans-serif"><b><br></b></font></div><div><div><div><font face="arial, sans-serif"><b>Title:</b>      Some Applications and Limitations of Convex Optimization Hierarchies for Discrete and Continuous Optimization Problems<br><br><b>Abstract:</b> </font><span style="font-family:arial,sans-serif">This thesis explores algorithmic applications and limitations of convex relaxation hierarchies for approximating some discrete and continuous optimization problems. </span></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">- We show a dichotomy of approximability of constraint satisfaction problems (CSPs) by linear programming (LP) relaxations: for every CSP, the approximation obtained by a basic LP relaxation, is no weaker than the approximation obtained using relaxations given by super-constant levels of the Sherali-Adams hierarchy on instances of size $n$.</font></div><div><font face="arial, sans-serif"><br></font></div><div><font face="arial, sans-serif">- For the problem of approximating the absolute maximum of an n-variate degree-d homogeneous polynomial f with real coefficients over the unit sphere, we analyze the optimum value of the level-t sum-of-squares (SoS) SDP relaxation of the problem. Our results offer a trade-off between the approximation ratio and running time, which can take advantage of additional structure in the polynomial, such as non-negativity or sparsity of the coefficients.</font></div><div><font face="arial, sans-serif"><br></font><div><font face="arial, sans-serif"><span> </span>- We study the problem of approximating the $p \to q$-norm of a matrix $A$, and prove the first NP-hardness result for approximating norms in the hypercontractive case $1< p < q < \infty$. We also prove almost tight algorithmic results for the case when $p \geq q$ (with $2 \in [q,p]$) where constant factor approximations for the matrix norms are possible.</font></div><div><font face="arial, sans-serif"><br></font></div><font face="arial, sans-serif">A common theme for these results is their connection to geometry. For the discrete optimization problem of CSP, geometry appears as a crucial tool for our lower bound proof. For the problem of polynomial optimization, we show that SDPs capture and extend earlier algorithms based on diameter estimation for convex bodies. For the matrix (operator) norm problem, the definition itself is geometric in nature and embedding theorems play a crucial role in our proofs.</font><br></div></div><div><br></div><div><div class="gmail_default"><b>Thesis Committee: <a href="mailto:madhurt@ttic.edu" target="_blank">Madhur Tulsiani</a>, </b>Yury Makarychev, Aaron Potechin. </div><div class="gmail_default"><br></div></div></div></div></div></div><br clear="all"></div><div><br></div><div><br></div><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue, Rm 517</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL  60637</font></i><br></font></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">773-834-1757</font></i></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div>
</div>