TY - JOUR

T1 - A Robust khintchine inequality, and algorithms for computing optimal constants in fourier analysis and high-dimensional geometry

AU - De, Anindya

AU - Diakonikolas, Ilias

AU - Servedio, Rocco A.

N1 - Funding Information:
This author's research supported by NSF grants CCF-0915929 and CCF-1115703.
Publisher Copyright:
© 2016 Society for Industrial and Applied Mathematics.

PY - 2016

Y1 - 2016

N2 - 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 W ≤1[LTF], where the minimum is taken over all n-variable LTFs and all n ≥ 0. Benjamini, Kalai, and Schramm [Publ. Math. Inst. Hautes' Etudes Sci., 90 (1999), pp. 5-43] conjectured that the true value of W≤1[LTF] is 2/π. We make progress on this conjecture by proving that W≤1[LTF] ≥ 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 W≤1[LTFn] denote the minimum squared Fourier mass on the degree-0 and degree-1 coefficients of any n-variable LTF. We prove that for every η > 0, there is a value K = K(η) = poly(1/η) such that W≤1[LTF] ≤ W≤1[LTFK] ≤ W≤1[LTF] + η. This easily yields an algorithm that runs in time 2poly(1/η)and determines the value of W≤1[LTF] up to an additive error of ±η. We give an analogous structural result, and a similar 2poly(1/η)-time algorithm, to determine Tomaszewski's constant to within an additive error of ±η; 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.

AB - 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 W ≤1[LTF], where the minimum is taken over all n-variable LTFs and all n ≥ 0. Benjamini, Kalai, and Schramm [Publ. Math. Inst. Hautes' Etudes Sci., 90 (1999), pp. 5-43] conjectured that the true value of W≤1[LTF] is 2/π. We make progress on this conjecture by proving that W≤1[LTF] ≥ 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 W≤1[LTFn] denote the minimum squared Fourier mass on the degree-0 and degree-1 coefficients of any n-variable LTF. We prove that for every η > 0, there is a value K = K(η) = poly(1/η) such that W≤1[LTF] ≤ W≤1[LTFK] ≤ W≤1[LTF] + η. This easily yields an algorithm that runs in time 2poly(1/η)and determines the value of W≤1[LTF] up to an additive error of ±η. We give an analogous structural result, and a similar 2poly(1/η)-time algorithm, to determine Tomaszewski's constant to within an additive error of ±η; 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.

KW - Fourier analysis

KW - Halfspaces

KW - Hyperplanes

KW - Khintchine inequality

KW - Linear threshold functions

UR - http://www.scopus.com/inward/record.url?scp=84976907462&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84976907462&partnerID=8YFLogxK

U2 - 10.1137/130919143

DO - 10.1137/130919143

M3 - Article

AN - SCOPUS:84976907462

SN - 0895-4801

VL - 30

SP - 1058

EP - 1094

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -