A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry

Anindya De, Ilias Diakonikolas, Rocco Servedio

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 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 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.

Original languageEnglish
Title of host publicationAutomata, Languages, and Programming
Subtitle of host publication40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I
EditorsFedorV. Fomin, Rūsiņš Freivalds, Marta Kwiatkowska, David Peleg
PublisherSpringer Berlin Heidelberg
Pages376-387
Number of pages12
Volume7965
ISBN (Electronic)978-3-642-39206-1
ISBN (Print)978-3-642-39205-4
DOIs
Publication statusPublished - 2013

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
Volume7965

Fingerprint

Dive into the research topics of 'A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry'. Together they form a unique fingerprint.

Cite this