TY - GEN

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

PY - 2013/7/23

Y1 - 2013/7/23

N2 - This paper makes two contributions towards determining some well-studied optimal constants in Fourier analysis of Boolean functions and high-dimensional geometry. 1. It has been known since 1994 [GL94] 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≤1[LTF], where the minimum is taken over all n-variable linear threshold functions and all n ≥ 0. Benjamini, Kalai and Schramm [BKS99] have 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. 2 We give an algorithm with the following property: given any η > 0, the algorithm runs in time 2 poly(1/η) and determines the value of W ≤1[LTF] up to an additive error of ±η. We give a similar 2 poly(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 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 [HK92] and independently by Ben-Tal, Nemirovski and Roos [BTNR02]. Our algorithms combine tools from anti-concentration of sums of independent random variables, Fourier analysis, and Hermite analysis of linear threshold functions.

AB - This paper makes two contributions towards determining some well-studied optimal constants in Fourier analysis of Boolean functions and high-dimensional geometry. 1. It has been known since 1994 [GL94] 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≤1[LTF], where the minimum is taken over all n-variable linear threshold functions and all n ≥ 0. Benjamini, Kalai and Schramm [BKS99] have 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. 2 We give an algorithm with the following property: given any η > 0, the algorithm runs in time 2 poly(1/η) and determines the value of W ≤1[LTF] up to an additive error of ±η. We give a similar 2 poly(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 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 [HK92] and independently by Ben-Tal, Nemirovski and Roos [BTNR02]. Our algorithms combine tools from anti-concentration of sums of independent random variables, Fourier analysis, and Hermite analysis of linear threshold functions.

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

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

U2 - 10.1007/978-3-642-39206-1_32

DO - 10.1007/978-3-642-39206-1_32

M3 - Conference contribution

AN - SCOPUS:84880315305

SN - 9783642392054

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 376

EP - 387

BT - Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings

T2 - 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013

Y2 - 8 July 2013 through 12 July 2013

ER -