[CS] Neng Huang Dissertation Defense/May 30, 2024

[via cs]

This is an announcement of Neng Huang's Dissertation Defense.
===============================================
Candidate: Neng Huang

Date: Thursday, May 30, 2024

Time: 10 am CT

Location: JCL 390

Title: New Results on the Approximability of Some Classical Constraint Satisfaction Problems

Abstract: In a constraint satisfaction problem (CSP), we are given a set of variables and a set of constraints over these variables and the goal is to assign the variables so that as many constraints as possible are satisfied. Many problems in computer science can be phrased in this language so it is of great interest to either design efficient algorithms for this task or prove that such algorithms don't exist. 

    In a breakthrough result, Raghavendra proved that for all CSPs there is a canonical semi-definite programming (SDP) relaxation that is optimal under the famous Unique Games Conjecture (UGC). More specifically, any integrality gap instances for this SDP relaxation can be turned into hardness results assuming UGC and there is a polynomial time rounding algorithm that achieves the integrality gap curve. However, this result does not tell us how to explicitly construct integrality gap instances for this SDP or what the optimal approximation ratio is for a given CSP. Moreover, the rounding algorithm has a doubly exponential dependency on the error parameter, which makes it practically infeasible.

    Based on Raghavendra's framework, we study the approximability for some classical CSPs, including MAX DI-CUT, MAX 2-SAT and its subproblems, and MAX NAE-SAT. In particular, assuming UGC, we show that MAX DI-CUT is strictly harder to approximate than MAX CUT and MAX NAE-SAT does not have a 7/8-approximation algorithm. To do so, we construct explicit integrality gap instances for the canonical SDP relaxation for these problems. For MAX 2-SAT and its subproblems, we give tight approximability results (modulo UGC) by presenting matching approximation algorithms and hardness results.

Advisors: Aaron Potechin

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