Generalized Samorodnitsky Noisy Function Inequalities, with Applications to Error-Correcting Codes

An inequality by Samorodnitsky states that if f:F2n → ℝ is a nonnegative function, and S ⊆ [n] is chosen by randomly including each coordinate with probability a certain λ = λ(q,ρ) < 1, then log||Tρf||q ≤ ES log||E(f|S)||q. Samorodnitsky’s inequality has several applications to the theory of error-correcting codes. Perhaps most notably, it can be used to show that any binary linear code (with minimum distance ω(logn)) that has vanishing decoding error probability on the BEC(λ) (binary erasure channel) also has vanishing decoding error on all memoryless symmetric channels with capacity above some C = C(λ).