[Colloquium] Reminder - Goutham Rajendran Candidacy Exam/Sep 29, 2021

[meganwoodward at uchicago.edu]

This is an announcement of Goutham Rajendran's Candidacy Exam.
===============================================
Candidate: Goutham Rajendran

Date: Wednesday, September 29, 2021

Time: 10:30 am CST

Remote Location: https://uchicago.zoom.us/j/99066499509?pwd=aEwrM2lrMVhDK1RIS20rajVCSlZpdz09 Meeting ID: 990 6649 9509 Passcode: 007482

Title: Computational hardness via Sum-of-Squares lower bounds

Abstract: The Sum-of-Squares (SoS) hierarchy is a powerful optimization technique that harnesses the power of semidefinite programming. It is a series of convex relaxations that progressively gets stronger in approximation, at the cost of running time. Due to its tremendous success and ability to capture a wide variety of algorithmic reasoning, evidence for computational hardness for an average-case problem, when NP-hardness is unavailable, can be obtained by showing lower bounds against the SoS hierarchy. In this talk, we take the fundamental certification problems of the Sherrington-Kirkpatrick Hamiltonian and Tensor/Sparse PCA and present a high-level overview of the techniques that go into showing SoS lower bounds for these problems.

Advisors: Aaron Potechin and Madhur Tulsiani

Committee Members: Aaron Potechin, Janos Simon, and Madhur Tulsiani