Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR18-168 | 25th September 2018 18:00

#### An upper bound on $\ell_q$ norms of noisy functions

TR18-168
Authors: Alex Samorodnitsky
Publication: 7th October 2018 16:43
Let $T_{\epsilon}$ be the noise operator acting on functions on the boolean cube $\{0,1\}^n$. Let $f$ be a nonnegative function on $\{0,1\}^n$ and let $q \ge 1$. We upper bound the $\ell_q$ norm of $T_{\epsilon} f$ by the average $\ell_q$ norm of conditional expectations of $f$, given sets of roughly $(1-2\epsilon)^{r(q)} \cdot n$ variables, where $r$ is an explicitly defined function of $q$.