An Upper Bound on $\ell_q$ Norms of Noisy Functions
Alex Samorodnitsky · IEEE Transactions on Information Theory · 2019
Let T∈, 0 ≤ ∈ ≤ 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}nand let q ≥ 1. We upper bound the ℓqnorm of T∈f by the average ℓqnorm of conditional expectations of f, given sets of roughly (1 - 2∈)r(q)· 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 BEC-capacity achieving binary linear codes and their duals. This improves the known bounds on the linear-weight components of the weight distribution of constant rate binary Reed-Muller codes for all (constant) rates.