Rich -to- Games conjecture
Rich -to- Games conjecture
Let be a Rich -to- Games instance with and . For each , the distribution of partitions of induced by uniformly sampled incident constraints is uniform over all partitions of into pairs. Let denote the promise problem distinguishing instances with an assignment satisfying all constraints from instances in which every assignment satisfies at most a fraction of the constraints. Rich -to- Games conjecture. For every , there is a sufficiently large even such that is NP-hard. This stronger variant was proposed to support hardness results for satisfiable instances and to provide additional structure beyond ordinary -to- 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
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.