Code Sparsification and its Applications

Sanjeev Khanna, Aaron L Putterman, Madhu Sudan

We introduce a notion of code sparsification that generalizes the notion of cut sparsification in graphs. For a (linear) code $\mathcal{C}\subseteq {\mathbb{F}}_q^n$ of dimension $k…