An upper bound on ℓ_q norms of noisy functions
share
Let T_ϵ 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 > 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.
READ FULL TEXT
