<div dir="ltr"><div><font color="#3c4043" face="Roboto, Arial, sans-serif"><span style="font-size:14px;letter-spacing:0.2px">Hi all — theory lunch is starting up again <b>today at 12:30pm in JCL 390</b>, with our own Neng Huang giving a talk! Details below — hope to see you all there.</span></font></div><div><font color="#3c4043" face="Roboto, Arial, sans-serif"><span style="font-size:14px;letter-spacing:0.2px"><br></span></font></div><div><font color="#3c4043" face="Roboto, Arial, sans-serif"><span style="font-size:14px;letter-spacing:0.2px">******
<b>
Date: </b>January 24, 2024</span></font></div><div><font color="#3c4043" face="Roboto, Arial, sans-serif"><span style="font-size:14px;letter-spacing:0.2px"><b>Time: </b>12:30pm CT</span></font></div><div><font color="#3c4043" face="Roboto, Arial, sans-serif"><span style="font-size:14px;letter-spacing:0.2px"><b>Location: </b>JCL 390</span></font></div><div><font color="#3c4043" face="Roboto, Arial, sans-serif"><span style="font-size:14px;letter-spacing:0.2px"><br></span></font></div><div><font color="#3c4043" face="Roboto, Arial, sans-serif"><span style="font-size:14px;letter-spacing:0.2px"><b>Title: </b></span></font><span style="color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;font-size:14px;letter-spacing:0.2px">Tight Approximability of MAX 2-SAT and Relatives, Under UGC</span></div><div><span style="color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;font-size:14px;letter-spacing:0.2px"><br></span></div><div><font color="#3c4043" face="Roboto, Arial, sans-serif"><span style="font-size:14px;letter-spacing:0.2px"><b>Speaker: </b>Neng Huang (UChicago)</span></font></div><div><font color="#3c4043" face="Roboto, Arial, sans-serif"><span style="font-size:14px;letter-spacing:0.2px"><br></span></font></div><div><font color="#3c4043" face="Roboto, Arial, sans-serif"><span style="font-size:14px;letter-spacing:0.2px"><b>Abstract: </b></span></font><span style="color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;font-size:14px;letter-spacing:0.2px">Austrin [Aus07] showed that the approximation ratio ≈ 0.94016567 obtained by the MAX 2-SAT algorithm of Lewin, Livnat and Zwick [LLZ02] is optimal, modulo the Unique Games Conjecture (UGC) and modulo a Simplicity Conjecture which states that the worst performance of the algorithm is obtained on so called simple configurations. We prove the Simplicity Conjecture using a combination of analytic and computational tools, thereby showing the optimality of the LLZ approximation algorithm, relying only on the Unique Games Conjecture.We also present new approximation algorithms for two restrictions of the MAX 2-SAT problem. By adapting Austrin’s and our arguments for the MAX 2-SAT problem we show that these two approximation algorithms are also optimal, modulo only UGC. This completes a full characterization of the approximability of the MAX 2-SAT problem and its restrictions.</span></div><span style="color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;font-size:14px;letter-spacing:0.2px">
Based on joint work with Joshua Brakensiek and Uri Zwick.</span><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><div dir="ltr"></div></div></div></div></div>