[CS] Neng Huang MS Presentation/Feb 18, 2021

[pbaclawski at uchicago.edu]

This is an announcement of Neng Huang's MS Presentation.
===============================================
Date: Thursday, February 18, 2021

Time: 4:00pm CST

Location: Via Zoom

https://uchicago.zoom.us/j/96162242762?pwd=QTBjc3lHd3BiQ2ZxTXRuQXFoMzg1UT09
Meeting ID: 961 6224 2762
Passcode: 900167

M.S. Candidate: Neng Huang

M.S. Paper Title: Moment Functions of Rounding Schemes

Abstract: Rounding schemes are a crucial ingredient in designing approximation algorithms for constraint satisfaction problems via semi-definite programming. In this paper, we study moment functions of rounding schemes and how they can be used to analyze rounding schemes. In particular, we show the following two results.

The first is that MAX NAE-SAT has no 7/8-approximation algorithms, assuming Unique Games Conjecture (UGC). More specifically, we show that for MAX NAE-SAT instances with near perfect completeness that only have clauses of size 3 and 5, there is no approximation algorithm that achieves a ratio greater than 3(√21−4)/2 ≈ 0.8739, assuming UGC.

The second result is that a large class of presidential type predicates are approximable, which means that the constraint satisfaction problem defined by the presidential type predicate admits an approximation algorithm that does better than random.

Advisor: Aaron Potechin

Committee Members: Andy Drucker, Madhur Tulsiani, and Aaron Potechin