On the Hardness of the One-Sided Code Sparsifier Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914072756224000 |
|---|---|
| author | Grigorescu, Elena Moayyedi, Alice |
| author_facet | Grigorescu, Elena Moayyedi, Alice |
| contents | The notion of code sparsification was introduced by Khanna, Putterman and Sudan (arxiv.2311.00788), as an analogue to the the more established notion of cut sparsification in graphs and hypergraphs. In particular, for $α\in (0,1)$ an (unweighted) one-sided $α$-sparsifier for a linear code $\mathcal{C} \subseteq \mathbb{F}_2^n$ is a subset $S\subseteq [n]$ such that the weight of each codeword projected onto the coordinates in $S$ is preserved up to an $α$ fraction. Recently, Gharan and Sahami (arxiv.2502.02799) show the existence of one-sided 1/2-sparsifiers of size $n/2+O(\sqrt{kn})$ for any linear code, where $k$ is the dimension of $\mathcal{C}$. In this paper, we consider the computational problem of finding a one-sided 1/2-sparsifier of minimal size, and show that it is NP-hard, via a reduction from the classical nearest codeword problem. We also show hardness of approximation results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_03184 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Hardness of the One-Sided Code Sparsifier Problem Grigorescu, Elena Moayyedi, Alice Information Theory E.4; F.2.2 The notion of code sparsification was introduced by Khanna, Putterman and Sudan (arxiv.2311.00788), as an analogue to the the more established notion of cut sparsification in graphs and hypergraphs. In particular, for $α\in (0,1)$ an (unweighted) one-sided $α$-sparsifier for a linear code $\mathcal{C} \subseteq \mathbb{F}_2^n$ is a subset $S\subseteq [n]$ such that the weight of each codeword projected onto the coordinates in $S$ is preserved up to an $α$ fraction. Recently, Gharan and Sahami (arxiv.2502.02799) show the existence of one-sided 1/2-sparsifiers of size $n/2+O(\sqrt{kn})$ for any linear code, where $k$ is the dimension of $\mathcal{C}$. In this paper, we consider the computational problem of finding a one-sided 1/2-sparsifier of minimal size, and show that it is NP-hard, via a reduction from the classical nearest codeword problem. We also show hardness of approximation results. |
| title | On the Hardness of the One-Sided Code Sparsifier Problem |
| topic | Information Theory E.4; F.2.2 |
| url | https://arxiv.org/abs/2510.03184 |