Abstract of a paper by Steven Heilman, Aukosh Jagannath, and Assaf Naor
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
participants (1)
-
alspach@math.okstate.edu