On Rich 2-to-1 Games
summary
Defines an r-wise rich two-to-one label-cover variant where each left vertex induces a near-uniform distribution over 2-sized partitions of the left alphabet, and conjectures hardness for fully rich instances: distinguishing almost-satisfiable from ≤ε-satisfiable is NP-hard for large alphabets. Shows this imperfect-completeness version is equivalent to Unique Games Conjecture, while the perfect-completeness variant is strictly stronger. Proof reduces via standard PCP machinery and hinges on a new analytic lemma — projection preserves influences for low-degree functions — proved using a hypercontractive inequality on the symmetric group.
AI-written summary · about