Rich 22-to-11 Games conjecture

Let Ψ=(LR,E,ΣL,ΣR,Φ)\Psi=(L\cup R,E,\Sigma_L,\Sigma_R,\Phi) be a Rich 22-to-11 Games instance with ΣL=n|\Sigma_L|=n and ΣR=n/2|\Sigma_R|=n/2. For each uLu\in L, the distribution of partitions of ΣL\Sigma_L induced by uniformly sampled incident constraints is uniform over all partitions of ΣL\Sigma_L into pairs. Let Gap-Rich-2-to-1n[1,δ]{\sf Gap\text{-}Rich\text{-}2\text{-to-}1}_n[1,\delta] denote the promise problem distinguishing instances with an assignment satisfying all constraints from instances in which every assignment satisfies at most a δ\delta fraction of the constraints. Rich 22-to-11 Games conjecture. For every δ>0\delta>0, there is a sufficiently large even nNn\in\mathbb{N} such that Gap-Rich-2-to-1n[1,δ]{\sf Gap\text{-}Rich\text{-}2\text{-to-}1}_n[1,\delta] is NP-hard. This stronger variant was proposed to support hardness results for satisfiable instances and to provide additional structure beyond ordinary 22-to-11 Games; the supplied text gives no resolution status.

Sources & referencesView supporting material

Primary source

Mark Braverman, Subhash Khot, Noam Lifshitz and Dor Minzer, “An Invariance Principle for the Multi-slice, with Applications”, arXiv:2110.10725 (2025).

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.