A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry.
A. De and I. Diakonikolas and R. Servedio.
40th International Colloquium on Automata, Languages and Programming (ICALP), 2013, pp. 376--387.

Abstract:

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 \cite{GL:94} that every linear threshold function has squared Fourier mass at least $1/2$ on its degree-$0$ and degree-$1$ coefficients. Denote the minimum such Fourier mass by $\w^{\leq 1}[\ltf]$, where the minimum is taken over all $n$-variable linear threshold functions and all $n \ge 0$. Benjamini, Kalai and Schramm \cite{BKS:99} have conjectured that the true value of $\w^{\leq 1}[\ltf]$ is $2/\pi$. We make progress on this conjecture by proving that $\w^{\leq 1}[\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.

• We give an algorithm with the following property: given any $\eta > 0$, the algorithm runs in time $2^{\poly(1/\eta)}$ and determines the value of $\w^{\leq 1}[\ltf]$ up to an additive error of $\pm\eta$. We give a similar $2^{{\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 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 \cite{HK92} and independently by Ben-Tal, Nemirovski and Roos \cite{BNR02}.
• Our algorithms combine tools from anti-concentration of sums of independent random variables, Fourier analysis, and Hermite analysis of linear threshold functions.

pdf of conference version

pdf of full version