Khot's Unique Games Conjecture in transversal-polynomial form

Let XαX^{\alpha} be an rr-fold cover of a graph XX, where ξ(Xα,t)\xi(X^{\alpha},t) is the transversal polynomial and deg(ξ(Xα,t))\deg(\xi(X^{\alpha},t)) is the maximum number of edges satisfied by a labelling of XX. For all ϵ,δ>0\epsilon,\delta>0, there exists r=r(ϵ,δ)r=r(\epsilon,\delta) such that, given an rr-fold cover XαX^{\alpha} of a graph XX, it is NP-hard to distinguish between the following two cases:

  1. deg(ξ(Xα,t))(1ϵ)E(X)\deg(\xi(X^{\alpha},t))\geq(1-\epsilon)|E(X)|;
  2. deg(ξ(Xα,t))δE(X)\deg(\xi(X^{\alpha},t))\leq\delta|E(X)|.

This is the Unique Games Conjecture, a central complexity-theoretic hypothesis whose truth would imply optimality results for approximation algorithms for several NP-hard problems. In this formulation, the degree of the transversal polynomial records the maximum number of edges satisfied by a labelling; the source provides no resolution of the conjecture.

Sources & referencesView supporting material

Primary source

Chris Godsil, Krystal Guo and Gordon Royle, “Transversal polynomial of r-fold covers”, arXiv:1910.05478 (2022).

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.