[Theory] [Theory Lunch] Neng Huang, Wednesday 1/24 12:30pm-1:30pm, JCL 390

[Gabe Schoenbach]

Hi all — theory lunch is starting up again *today at 12:30pm in JCL 390*,
with our own Neng Huang giving a talk! Details below — hope to see you all
there.

****** * Date: *January 24, 2024
*Time: *12:30pm CT
*Location: *JCL 390

*Title: *Tight Approximability of MAX 2-SAT and Relatives, Under UGC

*Speaker: *Neng Huang (UChicago)

*Abstract: *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.
Based on joint work with Joshua Brakensiek and Uri Zwick.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20240124/8de43acd/attachment.html>