pith. sign in

arxiv: 1112.2993 · v2 · pith:X2S3GIZQnew · submitted 2011-12-13 · 💻 cs.CC · math.FA· math.MG

Solution of the propeller conjecture in mathbb{R}³

classification 💻 cs.CC math.FAmath.MG
keywords mathbbcenteredconjecturepartitionproblempropellertimesbound
0
0 comments X
read the original abstract

It is shown that every measurable partition ${A_1,..., A_k}$ of $\mathbb{R}^3$ satisfies $$\sum_{i=1}^k||\int_{A_i} xe^{-\frac12||x||_2^2}dx||_2^2\le 9\pi^2.\qquad(*)$$ Let ${P_1,P_2,P_3}$ be the partition of $\mathbb{R}^2$ into $120^\circ$ sectors centered at the origin. The bound is sharp, with equality holding if $A_i=P_i\times \mathbb{R}$ for $i\in {1,2,3}$ and $A_i=\emptyset$ for $i\in \{4,...,k\}$ (up to measure zero corrections, orthogonal transformations and renumbering of the sets $\{A_1,...,A_k\}$). This settles positively the 3-dimensional Propeller Conjecture of Khot and Naor (FOCS 2008). The proof of 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 $(*)$ 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}$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.