Solution of the propeller conjecture in R^3

DOI10.1007/S00454-013-9530-0zbMATH Open1279.28019OpenAlexW2963064400WikidataQ122877638 ScholiaQ122877638MaRDI QIDQ368772FDOQ368772

Authors: Steven Heilman, Aukosh Jagannath, Assaf Naor

Publication date: 23 September 2013

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: It is shown that every measurable partition

A_{1}, ..., A_{k}

of

m a t h b b R^{3}

satisfies

sum_{i=1}^k||int_{A_i} xe^{-frac12||x||_2^2}dx||_2^2le 9pi^2.qquad(*)

Let

P_{1}, P_{2}, P_{3}

be the partition of

m a t h b b R^{2}

into

12 0^{c} i r c

sectors centered at the origin. The bound is sharp, with equality holding if

A_{i} = P_{i} i m e s m a t h b b R

for

i i n 1, 2, 3

and

A_{i} = e m p t y s e t

for

i i n 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 i m e s 4

centered and spherical hypothesis matrix equals

f r a c 2 p i 3

.

Full work available at URL: https://arxiv.org/abs/1112.2993

Recommendations

zbMATH Keywords

optimization complexity Gaussian measure measurable partition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Set functions and measures and integrals in infinite-dimensional spaces (Wiener measure, Gaussian measure, etc.) (28C20)

Cites Work

Cited In (3)

Uses Software

kepler98

This page was built for publication: Solution of the propeller conjecture in \(\mathbb R^3\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q368772)