Solution of the Propeller Conjecture in ℝ3

Steven Heilman, Aukosh Jagannath, Assaf Naor

Research output: Contribution to journalArticle

2 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)263-305
Number of pages43
JournalDiscrete and Computational Geometry
Volume50
Issue number2
DOIs
StatePublished - Sep 1 2013
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

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

  • Cite this