Reduction From Non-Unique Games To Boolean Unique Games
summary
Presents a polynomial-time reduction that fixes the 2016 construction by replacing periodic half‑spaces with ordinary half‑spaces and reduces a conjectured NP‑hard problem called Subspaces Near Intersection to Boolean Unique Games, contingent on that problem’s hardness. Proves soundness via a new low‑degree concentration theorem showing the degree‑≤d part on a random hyperplane matches the global part up to a tight 1/K bound, and explains why SDP only achieves the √δ barrier.
AI-written summary · about