Abstract of a paper by Steven Heilman, Aukosh Jagannath, and Assaf Naor - Banach

29 Dec 2011


      This is an announcement for the paper "Solution of the propeller
conjecture in $\R^3$" by Steven Heilman, Aukosh Jagannath, and Assaf Naor.
Abstract: It is shown that every measurable partition ${A_1,\ldots,
A_k}$ of $\R^3$ satisfies
  \begin{equation}\label{eq:abs} \sum_{i=1}^k\left|\int_{A_i}
xe^{-\frac12|x|_2^2}dx\right|_2^2\le 9\pi^2. \end{equation}
  Let ${P_1,P_2,P_3}$ be the partition of $\R^2$ into $120^\circ$
sectors centered at the origin. The bound~\eqref{eq:abs} is sharp,
with equality holding if $A_i=P_i\times \R$ for $i\in {1,2,3}$
and $A_i=\emptyset$ for $i\in {4,\ldots,k}$ (up to measure
zero corrections, orthogonal transformations and renumbering
of the sets ${A_1,\ldots,A_k}$). This settles positively
the $3$-dimensional Propeller Conjecture of Khot and Naor (FOCS
2008). The proof of~\eqref{eq:abs} 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~\eqref{eq:abs} is complexity-theoretic: the Unique Games hardness
threshold of the Kernel Clustering problem with $4\times 4$ centered
and spherical hypothesis matrix equals $\frac{2\pi}{3}$.
Archive classification: cs.DS math.FA math.MG
Submitted from: naor@cims.nyu.edu
The paper may be downloaded from the archive by web browser from URL
http://front.math.ucdavis.edu/1112.2993
or
http://arXiv.org/abs/1112.2993