[Colloquium] Christopher Jones Dissertation Defense/May 25, 2022

[Megan Woodward]

This is an announcement of Christopher Jones's Dissertation Defense.
===============================================
Candidate: Christopher Jones

Date: Wednesday, May 25, 2022

Time: 11 am CST

Remote Location: https://urldefense.com/v3/__https://uchicago.zoom.us/j/91364125151?pwd=RzVCcC9DOVU0aGN2M3MvREt2OU1LZz09__;!!BpyFHLRN4TMTrA!76XNT-U7v8LX_J_KAMB_LCPhoUSgt1Fe24h1lAtIPia80vDPqpu1QvQhKxzkYLoePDFyDP6QQwMua3jOQq-gC_Y$

Location: JCL 298

Title: Symmetrized Fourier Analysis of Convex Relaxations for Combinatorial Optimization Problems

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.

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

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.

Advisors: Aaron Potechin

Committee Members: Madhur Tulsiani, Aaron Potechin, and Laci Babai


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220524/90950b97/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PhD_thesis.pdf
Type: application/pdf
Size: 2725666 bytes
Desc: PhD_thesis.pdf
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20220524/90950b97/attachment-0001.pdf>