- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs? by Subhash Khot, Guy Kindler, Elchanan Mossel and Ryan O’Donnell
- Noise stability of functions with low influences: Invariance and optimality by Elchanan Mossel, Ryan O’Donnell and Krzysztof Oleszkiewicz

Khot and Oded Regev show that under the unique games conjecture that essentially the best algorithm for approximating vertex cover is to take all the vertices involved in a maximal matching.

Prasad Raghavendra gives a simple semidefinite programming approximation algorithm for any constraint satisfaction problem which is optimal under the UGC.

Sanjeev Arora, Boaz Barak and David Steurer describe an algorithm that given a unique game where 1-δ fraction of the edges can be satisfied, you can in time 2

^{npoly(δ)}find a coloring that satisfies a constant fraction of edges. This may or may not give evidence against the UGC.

Luca Trevisan has a nice recent survey on the unique games conjecture, covering much of the above and more, including beautiful connections between unique games and semidefinite programming.

As Lance has already tweeted, the STOC 2014 accepted papers list has been out for about a week. Though it currently re-directs to the local arrangements website at Columbia, this is the first use of the acm-stoc.org web address which will be the future direct link to all STOC conferences.

ReplyDelete