Title | ||
---|---|---|
A robust khintchine inequality, and algorithms for computing optimal constants in fourier analysis and high-dimensional geometry |
Abstract | ||
---|---|---|
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 c0. 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 2poly(1/η) and determines the value of W≤1[LTF] up to an additive error of ±η. We give 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 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. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1137/130919143 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
absolute constant c0,linear threshold function,fourier analysis,robust khintchine inequality,hermite analysis,time algorithm,n-variable linear threshold function,additive error,fourier mass,high-dimensional geometry,well-studied optimal constant,functional analysis | Boolean function,Square (algebra),Fourier analysis,Khintchine inequality,Hermite polynomials,Fourier transform,Hyperplane,Geometry,Discrete mathematics,Combinatorics,Algorithm,Physical constant,Mathematics | Conference |
Volume | Issue | ISSN |
30 | 2 | 0895-4801 |
Citations | PageRank | References |
2 | 0.37 | 14 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Anindya De | 1 | 239 | 24.77 |
Ilias Diakonikolas | 2 | 776 | 64.21 |
Rocco A. Servedio | 3 | 1656 | 133.28 |