Solution of the propeller conjecture in $\R^3$

Details Solution of the propeller conjecture in $\R^3$ Solution of the propeller conjecture in $\R^3$

2011-12-13

arxiv.org/abs/1112.2993v1

Computer Science

Computational Complexity

Scientific paper

It is shown that every measurable partition ${A_1,..., A_k}$ of $\R^3$ satisfies \sum_{i=1}^k|\int_{A_i} xe^{-\frac12|x|_2^2}dx|_2^2\le 9\pi^2. Let ${P_1,P_2,P_3}$ be the partition of $\R^2$ into $120^\circ$ sectors centered at the origin. The bound 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,...,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 \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}$.

Affiliated with

Also associated with

No associations

Rating

Solution of the propeller conjecture in $\R^3$ does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Solution of the propeller conjecture in $\R^3$, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solution of the propeller conjecture in $\R^3$ will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-490109