Penn Arts & Sciences Logo

Probability and Combinatorics

Thursday, September 24, 2015 - 2:30pm

Steven Heilman

UCLA

Location

University of Pennsylvania

DRL 3C8

*Abstract:* We study contraction under a Markov semi-group and influence bounds for functions all of whose low level Fourier coefficients vanish. This study is motivated by the explicit construction of 3-regular expander graphs of Mendel and Naor, though our results have no direct implication for the construction of expander graphs.

In the positive direction we prove an $L_{p}$ Poincar\A'{e} inequality and moment decay estimates for mean $0$ functions and for all $1

<\infty$, proving the degree one case of a conjecture of Mendel and Naor as well as the general degree case of the conjecture when restricted to Boolean functions. In the negative direction, we answer negatively two questions of Hatami and Kalai concerning extensions of the Kahn-Kalai-Linial and Harper Theorems to tail spaces. For example, we construct a function $f\colon\{-1,1\}^{n} o\{-1,1\}$ whose Fourier coefficients vanish up to level $c \log n$, with all influences bounded by $C \log n/n$ for some constants $0