<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
</head>
<body>
<div class="BodyFragment"><font size="2"><span style="font-size:11pt;">
<div class="PlainText">This is an announcement of Christopher Jones's Dissertation Defense.<br>
===============================================<br>
Candidate: Christopher Jones<br>
<br>
Date: Wednesday, May 25, 2022<br>
<br>
Time: 11 am CST<br>
<br>
Remote Location: <a href="https://urldefense.com/v3/__https://uchicago.zoom.us/j/91364125151?pwd=RzVCcC9DOVU0aGN2M3MvREt2OU1LZz09__;!!BpyFHLRN4TMTrA!76XNT-U7v8LX_J_KAMB_LCPhoUSgt1Fe24h1lAtIPia80vDPqpu1QvQhKxzkYLoePDFyDP6QQwMua3jOQq-gC_Y$">
https://urldefense.com/v3/__https://uchicago.zoom.us/j/91364125151?pwd=RzVCcC9DOVU0aGN2M3MvREt2OU1LZz09__;!!BpyFHLRN4TMTrA!76XNT-U7v8LX_J_KAMB_LCPhoUSgt1Fe24h1lAtIPia80vDPqpu1QvQhKxzkYLoePDFyDP6QQwMua3jOQq-gC_Y$</a><br>
<br>
Location: JCL 298<br>
<br>
Title: Symmetrized Fourier Analysis of Convex Relaxations for Combinatorial Optimization Problems
<br>
<br>
Abstract: Convex relaxations are a central tool in modern algorithm design, but mathematically analyzing the performance of a convex relaxation has remained difficult. We develop Fourier analytic methods for the study of convex relaxations, with special focus
on semidefinite programming and the sum-of-squares hierarchy.<br>
<br>
We prove two concrete sum-of-squares lower bounds: first, that sum-of-squares cannot certify the ground states of the Sherrington-Kirkpatrick model, and second, that sum-of-squares cannot certify the size of the maximum independent set in a sparse random graph.
Both proofs involve significant extensions of the "pseudocalibration plus graph matrix analysis" approach pioneered by Barak et al [FOCS16].<br>
<br>
Outside of the setting of the sum-of-squares hierarchy, we give two other major contributions. First, we introduce a new basis of inner product polynomials, which form a Fourier-like basis that exhibits many beautiful combinatorial properties related to the
topology of an underlying graph. Second, we give a new approach to an important open problem in the theory of error-correcting codes, based on convex relaxations.
<br>
<br>
Advisors: Aaron Potechin<br>
<br>
Committee Members: Madhur Tulsiani, Aaron Potechin, and Laci Babai<br>
<br>
</div>
</span></font></div>
<div class="BodyFragment"><font size="2"><span style="font-size:11pt;">
<div class="PlainText"><br>
<br>
</div>
</span></font></div>
</body>
</html>