An upper bound on ℓ_q norms of noisy functions

2018/09/25 by Samorodnitsky, Alex
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.1809.09696

Abstract

Let T_ε 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. We upper bound the ℓ_q norm of T_ε f by the average ℓ_q norm 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 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.

Related

• An improved bound on ℓ_q norms of noisy functions
• Generalized Samorodnitsky noisy function inequalities, with applications to error-correcting codes
• On the entropy of a noisy function
• Breaking the ε-Soundness Bound of the Linearity Test over GF(2)
• On codes decoding a constant fraction of errors on the BSC