Khot's unique games conjecture
Khot's unique games conjecture
Let be a positive integer, and consider an instance of the two-variable linear system -Lin- over , with equations
An assignment is a map with each variable taking a value in . Unique games conjecture. For every , given an instance in which a fraction of equations can be satisfied, there exists a value of such that no polynomial-time algorithm can find a solution satisfying at least an 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.