论文标题
$ \ ell_q $噪声功能的$ \ ell_q $规范的改进限制
An improved bound on $\ell_q$ norms of noisy functions
论文作者
论文摘要
令$t_ε$，$ 0 \leε\ le 1/2 $，是噪声运算符，该噪声运算符在布尔值$ \ {0,1 \}^n $上作用。令$ f $为$ \ {0,1 \}^n $的非负函数，让$ q \ ge 1 $。在ARXIV中：1809.09696 $ \ ell_q $ norm of $t_εf $的$ \ ell_q $有条件期望为$ f $的平均$ \ ell_q $规范的上限，给定的集合，其元素是随机选择的，概率$λ$，取决于$ q $，并以$ q $为基础。在本说明中，我们证明了这种不等式的整数$ q \ ge 2 $，具有更好的（较小）参数$λ$。新的不等式对于子润植物的特征功能很紧。 作为一个应用程序，在Arxiv：2008.07236之后，我们表明，芦苇量代码$ c $ r $ r $ $ r $解码在$ \ mathrm {bsc}（p）$上，如果\ [r〜 <〜1- log_2- \ log_2 \ weft（1 + \ \ \ sqrt {4p（1-p（1-p（1-p（1-p（1-p）， \]这是Arxiv：2008.07236的估计值的（次要）改进。
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.
