ECCC-Report TR18-168https://eccc.weizmann.ac.il/report/2018/168Comments and Revisions published for TR18-168en-usTue, 12 Nov 2019 09:06:44 +0200
Revision 1
| An upper bound on $\ell_q$ norms of noisy functions |
Alex Samorodnitsky
https://eccc.weizmann.ac.il/report/2018/168#revision1Let $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$.
We describe some applications for error-correcting codes and for matroids. In particular, we derive an upper bound on the weight distribution of duals of BEC-capacity achieving binary linear codes. This improves the known bounds on the linear-weight components of the weight distribution of constant rate binary Reed-Muller codes for almost all rates.Tue, 12 Nov 2019 09:06:44 +0200https://eccc.weizmann.ac.il/report/2018/168#revision1
Paper TR18-168
| An upper bound on $\ell_q$ norms of noisy functions |
Alex Samorodnitsky
https://eccc.weizmann.ac.il/report/2018/168Let $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$.
We describe some applications for error-correcting codes and for matroids. In particular, we derive an upper bound on the weight distribution of duals of BEC-capacity achieving binary linear codes. This improves the known bounds on the linear-weight components of the weight distribution of constant rate binary Reed-Muller codes for almost all rates.Sun, 07 Oct 2018 16:43:32 +0300https://eccc.weizmann.ac.il/report/2018/168