<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=us-ascii">
</head>
<body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">
<div class="elementToProof">This is an announcement of Neng Huang's Candidacy Exam.<span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
</span>===============================================<span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
</span>Candidate: Neng Huang<span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
<br class="">
</span>Date: Monday, December 04, 2023<span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
<br class="">
</span>Time: 2 pm CST<span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
<br class="">
</span>Location: JCL 236<span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
<br class="">
</span>Title: Rounding Schemes for Constraint Satisfaction Problems<span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
<br class="">
</span>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. <span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
<br class="">
</span>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.<span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
<br class="">
</span>Advisors: Aaron Potechin<span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt;" class=""><br class="">
<br class="">
</span></div>
<div class="elementToProof">Committee Members: Madhur Tulsiani, Aaron Potechin, and Janos Simon</div>
</body>
</html>