<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"><span style="letter-spacing: normal; font-family: Helvetica; font-size: 12px; font-weight: 400; color: rgb(0, 0, 0);">This is an announcement of Neng Huang's Candidacy Exam.</span><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
</span><span style="letter-spacing: normal; font-family: Helvetica; font-size: 12px; font-weight: 400; color: rgb(0, 0, 0);">===============================================</span><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
</span><span style="letter-spacing: normal; font-family: Helvetica; font-size: 12px; font-weight: 400; color: rgb(0, 0, 0);">Candidate: Neng Huang</span><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
<br>
</span><span style="letter-spacing: normal; font-family: Helvetica; font-size: 12px; font-weight: 400; color: rgb(0, 0, 0);">Date: Monday, December 04, 2023</span><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
<br>
</span><span style="letter-spacing: normal; font-family: Helvetica; font-size: 12px; font-weight: 400; color: rgb(0, 0, 0);">Time: 2 pm CST</span><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
<br>
</span><span style="letter-spacing: normal; font-family: Helvetica; font-size: 12px; font-weight: 400; color: rgb(0, 0, 0);">Location: JCL 236</span><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
<br>
</span><span style="letter-spacing: normal; font-family: Helvetica; font-size: 12px; font-weight: 400; color: rgb(0, 0, 0);">Title: Rounding Schemes for Constraint Satisfaction Problems</span><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
<br>
</span><span style="letter-spacing: normal; font-family: Helvetica; font-size: 12px; font-weight: 400; color: rgb(0, 0, 0);">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><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
<br>
</span><span style="letter-spacing: normal; font-family: Helvetica; font-size: 12px; font-weight: 400; color: rgb(0, 0, 0);">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><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
<br>
</span><span style="letter-spacing: normal; font-family: Helvetica; font-size: 12px; font-weight: 400; color: rgb(0, 0, 0);">Advisors: Aaron Potechin</span><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
<br>
</span></div>
<div class="elementToProof"><span style="letter-spacing: normal; font-family: Helvetica; font-size: 12px; font-weight: 400; color: rgb(0, 0, 0);">Committee Members: Madhur Tulsiani, Aaron Potechin, and Janos Simon</span></div>
<div id="Signature">
<div style="background-color: rgb(255, 255, 255);"><span style="font-family: Calibri, Helvetica, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><br>
</span></div>
</div>
</body>
</html>