On Khot's Unique Games Conjecture and an Application to Approximate Coloring

Oded Regev
Thursday, 23.3.2006, 14:30
Room 337-8 Taub Bld.

I will survey some of the recent developments surrounding Khot's "unique games conjecture", including applications and attempts to prove it. Time permitting, I will describe one recent application of this conjecture. Consider the approximate-coloring(q,Q) problem: Given a graph G, decide whether $chi(G) \le q$ or $chi(G) \ge Q$. We derive hardness for this problem for any constants $3 \le q < Q$, based on (variants of) the unique games conjecture. The proof is based on bounding various generalized noise-stability quantities using the invariance principle of Mossel et al [MOO'05]. This is joint work with Irit Dinur and Elchanan Mossel.

Back to the index of events