TY - JOUR
T1 - Solution of the Propeller Conjecture in ℝ3
AU - Heilman, Steven
AU - Jagannath, Aukosh
AU - Naor, Assaf
N1 - Funding Information:
S.H. and A.J. were supported by NSF Grant CCF-0832795 and NSF Graduate Research Fellowship DGE-0813964. A.N. was supported by NSF Grant CCF-0832795, BSF Grant 2006009, and the Packard Foundation. Part of this work was carried out when S.H. and A.N. were visiting the Quantitative Geometry program at MSRI
PY - 2013/9
Y1 - 2013/9
N2 - It is shown that every measurable partition {A1,...,Ak} ℝ3 satisfies, Let {P1, P2, P3} be the partition of ℝ2 into 120° sectors centered at the origin. The bound (1) is sharp, with equality holding if Ai = Pi × ℝ for i ∈ {1,2,3} and Ai = ∅ for i ∈ {4,...,k}. This settles positively the 3-dimensional Propeller Conjecture of Khot and Naor [(Mathematika 55(1-2):129-165, 2009 (FOCS 2008)]. The proof of (1) reduces the problem to a finite set of numerical inequalities which are then verified with full rigor in a computer-assisted fashion. The main consequence (and motivation) of (1) is complexity-theoretic: the unique games hardness threshold of the kernel clustering problem with 4 × 4 centered and spherical hypothesis matrix equals 2Π/3.
AB - It is shown that every measurable partition {A1,...,Ak} ℝ3 satisfies, Let {P1, P2, P3} be the partition of ℝ2 into 120° sectors centered at the origin. The bound (1) is sharp, with equality holding if Ai = Pi × ℝ for i ∈ {1,2,3} and Ai = ∅ for i ∈ {4,...,k}. This settles positively the 3-dimensional Propeller Conjecture of Khot and Naor [(Mathematika 55(1-2):129-165, 2009 (FOCS 2008)]. The proof of (1) reduces the problem to a finite set of numerical inequalities which are then verified with full rigor in a computer-assisted fashion. The main consequence (and motivation) of (1) is complexity-theoretic: the unique games hardness threshold of the kernel clustering problem with 4 × 4 centered and spherical hypothesis matrix equals 2Π/3.
UR - http://www.scopus.com/inward/record.url?scp=84881614344&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84881614344&partnerID=8YFLogxK
U2 - 10.1007/s00454-013-9530-0
DO - 10.1007/s00454-013-9530-0
M3 - Article
AN - SCOPUS:84881614344
SN - 0179-5376
VL - 50
SP - 263
EP - 305
JO - Discrete and Computational Geometry
JF - Discrete and Computational Geometry
IS - 2
ER -