2025/10/03 by Elena Grigorescu, Grigorescu, Elena, Alice Moayyedi +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #E.4 #F.2.2 #FOS: Computer and information sciences #Information Theory (cs.IT) #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.2510.03184
openalex publication_date 2025/10/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 α∈ (0,1) an (unweighted) one-sided α-sparsifier for a linear code C ⊆ \mathbbF2n is a subset S⊆ [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(√(kn)) for any linear code, where k is the dimension of 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.