Solution of the propeller conjecture in ℝ 3

Steven Heilman, Aukosh Jagannath, Assaf Naor

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

It is shown that every measurable partition {A 1,..., A k} of ℝ 3 satisfies (Equation Presented) Let {P 1,P 2,P 3} be the partition of ℝ 2 into 120° sectors centered at the origin. The bound (1) is sharp, with equality holding if A i=P i x ℝ for i ∈ {1,2,3} and A i = ∅ for i∈ {4,...,k}. This settles positively the 3-dimensional Propeller Conjecture of Khot and Naor (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 x 4 centered and spherical hypothesis matrix equals 2π/3.

Original languageEnglish (US)
Title of host publicationSTOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing
Pages269-276
Number of pages8
DOIs
StatePublished - 2012
Event44th Annual ACM Symposium on Theory of Computing, STOC '12 - New York, NY, United States
Duration: May 19 2012May 22 2012

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other44th Annual ACM Symposium on Theory of Computing, STOC '12
CountryUnited States
CityNew York, NY
Period5/19/125/22/12

Keywords

  • grothendieck inequalities
  • kernel clustering
  • semidefinite programming
  • unique games hardness

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Solution of the propeller conjecture in ℝ <sup>3</sup>'. Together they form a unique fingerprint.

Cite this