2026-10-01T07:51:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25536 2026-09-23T23:43:10Z ddc:004 open_access

On the Hardness of the One-Sided Code Sparsifier Problem Grigorescu, Elena Moayyedi, Alice Code sparsifiers NP-hardness Approximation hardness The notion of code sparsification was introduced by Khanna, Putterman and Sudan (SODA 2024) as an analogue to 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 𝒞 ⊆ 𝐅₂ⁿ 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 𝒞. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Elena Grigorescu and Alice Moayyedi 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.47 urn:nbn:de:0030-drops-255365 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.47 eng https://creativecommons.org/licenses/by/4.0/legalcode