Title : Computing some optimal constants in fourier analysis and high dimensional geometry 

Abstract : We consider two  well-studied constants in Fourier analysis and high-dimensional geometry and make progress towards determining their exact values. 

1. It has been known since 1994 (Gotsman and Linial) 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 \lambda(LTF) where the minimum is taken over all $n$-variable linear threshold functions and all $n \ge 0$, O'Donnell has conjectured that the true value of $\lambda(LTF)$ is $2/\pi$.

We make progress on this conjecture by proving that $\lambda(LTF) \geq 1/2 + c$ for some absolute constant $c>0$.
The key ingredient in our proof is a ``robust'' version of the well-known Khintchine-Kahane inequality in functional analysis, which we believe may be of independent interest.


2. We give an algorithm with the following property:  given any $\eta > 0$, the algorithm runs in time $2^{\poly(1/\eta)}$ and determines the value of $\lambda(LTF)$ up to an additive error of $+- \eta$.  We give a similar $2^{2^{\poly(1/\eta)}}$-time  algorithm to determine Tomaszewski's constant to within an additive error of $+- \eta$; 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  and  independently by Ben-Tal, Nemirovski and Roos. Our algorithms combine tools from anti-concentration of sums of independent random variables, Fourier analysis, and Hermite analysis of linear threshold functions.

Joint work with Ilias Diakonikolas and Rocco Servedio.