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

Original language | English |
---|---|

Title of host publication | Automata, Languages, and Programming |

Subtitle of host publication | 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I |

Editors | FedorV. Fomin, Rūsiņš Freivalds, Marta Kwiatkowska, David Peleg |

Publisher | Springer Berlin Heidelberg |

Pages | 376-387 |

Number of pages | 12 |

Volume | 7965 |

ISBN (Electronic) | 978-3-642-39206-1 |

ISBN (Print) | 978-3-642-39205-4 |

DOIs | |

Publication status | Published - 2013 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Berlin Heidelberg |

Volume | 7965 |