[Theory] 8/18 Thesis Defense: Mrinalkanti Ghosh, TTIC

[Mary Marre via Theory]

*When*:     Monday, August 18th from* 9:30 - 10:30**am CT*

*Virtually*: via *Zoom*
<https://uchicago.zoom.us/j/96150477778?pwd=xZuTIgvLuS5uqTDjhHgFnJztmfaPNg.1>


*Who:  *    Mrinalkanti Ghosh, TTIC


*Title:*      Some Applications and Limitations of Convex Optimization
Hierarchies for Discrete and Continuous Optimization Problems

*Abstract:* This thesis explores algorithmic applications and limitations
of convex relaxation hierarchies for approximating some discrete and
continuous optimization problems.

- 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$.

- 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.

- 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.

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.

*Thesis Committee: Madhur Tulsiani <madhurt at ttic.edu>, *Yury Makarychev,
Aaron Potechin.




Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue, Rm 517*
*Chicago, IL  60637*
*773-834-1757*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250812/99774288/attachment.html>