






















Let $T_ε$, $0 \le ε\le 1/2$, 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$. In arXiv:1809.09696 the $\ell_q$ norm of $T_ε f$ was upperbounded by the average $\ell_q$ norm of conditional expectations of $f$, given sets whose elements are chosen at random with probability $λ$, depending on $q$ and on $ε$. In this note we prove this inequality for integer $q \ge 2$ with a better (smaller) parameter $λ$. The new inequality is tight for characteristic functions of subcubes. As an application, following arXiv:2008.07236, we show that a Reed-Muller code $C$ of rate $R$ decodes errors on $\mathrm{BSC}(p)$ with high probability if \[ R ~<~ 1 - \log_2\left(1 + \sqrt{4p(1-p)}\right). \] This is a (minor) improvement on the estimate in arXiv:2008.07236.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。