An improved bound on ℓ_q norms of noisy functions

2020/10/06 by Alex Samorodnitsky, Samorodnitsky, Alex
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #FOS: Computer and information sciences #Information Theory (cs.IT) #Limits and Structures in Graph Theory #Mathematical Approximation and Integration

paper · pdf · doi:10.48550/arxiv.2010.02721

openalex publication_date 2020/10/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let T_ε, 0 ≤ ε≤ 1/2, be the noise operator acting on functions on the boolean cube \0,1\ⁿ. Let f be a nonnegative function on \0,1\ⁿ and let q ≥ 1. In arXiv:1809.09696 the ℓ_q norm of T_ε f was upperbounded by the average ℓ_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 ≥ 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 BSC(p) with high probability if \[ R ~

Related

• An upper bound on ℓ_q norms of noisy functions
• On the entropy of a noisy function
• Quantitative relation between noise sensitivity and influences
• Generalized Samorodnitsky noisy function inequalities, with applications to error-correcting codes
• A Noisy-Influence Regularity Lemma for Boolean Functions