<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
</head>
<body>
<div class="" style="word-wrap:break-word; line-break:after-white-space">
<div class=""><span class="" style="font-size:14.666666984558105px">This is an announcement of Christopher Jones's Dissertation Defense.</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">===============================================</span><br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Candidate: Christopher Jones</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Date: Wednesday, May 25, 2022</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Time: 11 am CST</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Remote Location: </span><a href="https://urldefense.com/v3/__https://uchicago.zoom.us/j/91364125151?pwd=RzVCcC9DOVU0aGN2M3MvREt2OU1LZz09__;!!BpyFHLRN4TMTrA!76XNT-U7v8LX_J_KAMB_LCPhoUSgt1Fe24h1lAtIPia80vDPqpu1QvQhKxzkYLoePDFyDP6QQwMua3jOQq-gC_Y$" class="" style="font-size:14.666666984558105px">https://urldefense.com/v3/__https://uchicago.zoom.us/j/91364125151?pwd=RzVCcC9DOVU0aGN2M3MvREt2OU1LZz09__;!!BpyFHLRN4TMTrA!76XNT-U7v8LX_J_KAMB_LCPhoUSgt1Fe24h1lAtIPia80vDPqpu1QvQhKxzkYLoePDFyDP6QQwMua3jOQq-gC_Y$</a><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Location: JCL 298</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Title: Symmetrized Fourier Analysis of Convex Relaxations for Combinatorial Optimization Problems </span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">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.</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">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].</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">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. </span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Advisors: Aaron Potechin</span><br class="" style="font-size:14.666666984558105px">
<br class="" style="font-size:14.666666984558105px">
<span class="" style="font-size:14.666666984558105px">Committee Members: Madhur Tulsiani, Aaron Potechin, and Laci Babai</span>
</div>
<div class=""><span class="" style="font-size:14.666666984558105px"><br class="">
</span></div>
<div class=""><span class="" style="font-size:14.666666984558105px"><br class="">
</span></div>
<div class=""><span class="" style="font-size:14.666666984558105px"></span></div>
</div>
<div class="" style="word-wrap:break-word; line-break:after-white-space">
<div class=""><span class="" style="font-size:14.666666984558105px"></span></div>
<br class="">
</div>
</body>
</html>