Khot's unique games conjecture

Let kk be a positive integer, and consider an instance of the two-variable linear system 22-Lin-kk over Zk\mathbb{Z}_k, with equations

xi=xj+bl(modk).\mathbf{x}_i=\mathbf{x}_j+\mathbf{b}_l\pmod{k}.

An assignment is a map x={x1,,xn}\mathbf{x}=\{\mathbf{x}_1,\ldots,\mathbf{x}_n\} with each variable taking a value in {0,,k1}\{0,\ldots,k-1\}. Unique games conjecture. For every 0<ϵ<120<\epsilon<\frac{1}{2}, given an instance in which a 1ϵ1-\epsilon fraction of equations can be satisfied, there exists a value of kk such that no polynomial-time algorithm can find a solution satisfying at least an ϵ\epsilon fraction of the equations. This is a central hardness assumption in approximation complexity and underlies optimality results for problems such as MAX-CUT. The source does not provide evidence resolving the conjecture.

Sources & referencesView supporting material

Primary source

Tuhin Sahai and Abeynaya Gnanasekaran, “On the Emergence of Ergodic Dynamics in Unique Games”, arXiv:2404.16024 (2024).

Additional references

3 papers in this index state this conjecture (2017–2024). The statement above is taken from the most recent of them; the others are arXiv:1803.06800, arXiv:1702.02885.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.