[Colloquium] Neng Huang Candidacy Exam/Dec 4, 2023

[meganwoodward at uchicago.edu]

This is an announcement of Neng Huang's Candidacy Exam.
===============================================
Candidate: Neng Huang

Date: Monday, December 04, 2023

Time:  2 pm CST

Location: JCL 236

Title: Rounding Schemes for Constraint Satisfaction Problems

Abstract: Constraint satisfaction problems (CSPs) are ubiquitous in computer science. One very successful paradigm for (approximately) solving these problems is via semi-definite programming (SDP). It first relaxes the original integer-valued problem to a vector-valued problem, which can be solved in polynomial time, and then uses some rounding algorithm to carefully construct an integer solution from the vector solution. 

In this presentation, I will focus on the second step of this paradigm. I will first describe the general brute-force rounding algorithm by Raghavendra and Steurer. The runtime of this algorithm, being polynomial when the desired accuracy eps is a constant, in fact has a terrible dependence on eps, which makes it impractical when eps is even just moderately small. I will then discuss some recent attempts at alternative routes, including a joint work on new rounding algorithms for MAX 2-CSPs.

Advisors: Aaron Potechin

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