Solution of the Propeller Conjecture in ℝ3

Steven Heilman; Aukosh Jagannath; Assaf Naor

doi:10.1007/s00454-013-9530-0

Solution of the Propeller Conjecture in ℝ³

Steven Heilman
, Aukosh Jagannath
, Assaf Naor

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

It is shown that every measurable partition {A₁,...,A_k} ℝ³ satisfies, Let {P₁, P₂, P₃} be the partition of ℝ² into 120^° sectors centered at the origin. The bound (1) is sharp, with equality holding if A_i = P_i × ℝ for i ∈ {1,2,3} and A_i = ∅ 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.

Original language	English (US)
Pages (from-to)	263-305
Number of pages	43
Journal	Discrete and Computational Geometry
Volume	50
Issue number	2
DOIs	https://doi.org/10.1007/s00454-013-9530-0
State	Published - Sep 2013
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1007/s00454-013-9530-0

Cite this

@article{6902c0c8e0374dce840a21e773225d6c,

title = "Solution of the Propeller Conjecture in ℝ3",

abstract = "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.",

author = "Steven Heilman and Aukosh Jagannath and Assaf Naor",

note = "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 ",

year = "2013",

month = sep,

doi = "10.1007/s00454-013-9530-0",

language = "English (US)",

volume = "50",

pages = "263--305",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "2",

}

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 - https://www.scopus.com/pages/publications/84881614344

UR - https://www.scopus.com/pages/publications/84881614344#tab=citedBy

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 -

Solution of the Propeller Conjecture in ℝ³

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this