<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<style type="text/css" style="display:none;"> P {margin-top:0;margin-bottom:0;} </style>
</head>
<body dir="ltr">
<div class="elementToProof" style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);">
This is an announcement of Neng Huang's Dissertation Defense.<br>
===============================================<br>
Candidate: Neng Huang<br>
<br>
Date: Thursday, May 30, 2024<br>
<br>
Time: 10 am CT<br>
<br>
Location: JCL 390<br>
<br>
Title: New Results on the Approximability of Some Classical Constraint Satisfaction Problems<br>
<br>
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. <br>
<br>
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.<br>
<br>
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.<br>
<br>
Advisors: Aaron Potechin<br>
<br>
Committee Members: Aaron Potechin, Madhur Tulsiani, and Janos Simon</div>
<div id="Signature">
<div style="background-color: rgb(255, 255, 255);"></div>
</div>
</body>
</html>