2012/07/10 by De, Anindya, Diakonikolas, Ilias, Servedio, Rocco A. · 1 citation
#Computational Complexity (cs.CC) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.1207.2229
This paper makes two contributions towards determining some well-studied optimal constants in Fourier analysis \newaof Boolean functions and high-dimensional geometry. \beginenumerate \item It has been known since 1994 \citeGL: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≤ 1[\ltf], where the minimum is taken over all n-variable linear threshold functions and all n ≥ 0. Benjamini, Kalai and Schramm \citeBKS:99 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. \item 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 \citeHK92 and independently by Ben-Tal, Nemirovski and Roos \citeBNR02. Our algorithms combine tools from anti-concentration of sums of independent random variables, Fourier analysis, and Hermite analysis of linear threshold functions. \endenumerate