A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry

This paper makes two contributions towards determining some well-studied optimal constants in Fourier analysis of Boolean functions and high-dimensional geometry. It has been known since 1994 [C. Gotsman and N. Linial, Combinatorica, 14 (1994), pp. 35--50] that every linear threshold function (LTF) has a squared Fourier mass of at least $1/2$ on its degree-$0$ and degree-$1$ coefficients. Let the minimum such Fourier mass be ${\bf W}^{\leq 1}[{\bf LTF}]$, where the minimum is taken over all $n$-variable LTFs and all $n \ge 0$. Benjamini, Kalai, and Schramm [Publ. Math. Inst. Hautes Études Sci., 90 (1999), pp. 5--43] conjectured that the true value of ${\bf W}^{\leq 1}[{\bf LTF}]$ is $2/\pi$. We make progress on this conjecture by proving that ${\bf W}^{\leq 1}[{\bf LTF}] \geq 1/2 + c$ for some absolute constant $c>0$. The key ingredient in our proof is a “robust” version of the well-known Khintchine inequality in functional analysis, which we believe may be of independent interest. Let ${\bf W}^{\leq 1}[{\bf LTF}_n]$ denote the minimum squared Fourier mass on the degree-$0$ and degree-$1$ coefficients of any $n$-variable LTF. We prove that for every $\eta > 0$, there is a value $K=K(\eta)=\mathrm{poly}(1/\eta)$ such that ${\bf W}^{\leq 1}[{\bf LTF}] \leq {\bf W}^{\leq 1}[{\bf LTF}_K] \leq {\bf W}^{\leq 1}[{\bf LTF}] + \eta.$ This easily yields an algorithm that runs in time $2^{\mathrm{poly}(1/\eta)}$ and determines the value of ${\bf W}^{\leq 1}[{\bf LTF}]$ up to an additive error of $\pm\eta$. We give an analogous structural result, and a similar $2^{{\mathrm{poly}(1/\eta)}}$-time algorithm, to determine Tomaszewski's constant to within an additive error of $\pm \eta$; this is the minimum (over all origin-centered hyperplanes $H$) fraction of points in $\{-1,1\}^n$ that lie within a Euclidean distance $1$ of $H$. Tomaszewski's constant is conjectured to be $1/2$; lower bounds on it have been given by Holzman and Kleitman [Combinatorica, 12 (1992), pp. 303--316] and independently by Ben-Tal, Nemirovski, and Roos [SIAM J. Optim., 13 (2002), pp. 535--560]. Our structural results combine tools from anticoncentration of sums of independent random variables, Fourier analysis, and Hermite analysis of LTFs.