Skip to content
Preprint

Hardness and Inapproximability of the Covering Radius for LDPC Codes

Nov 2026 · 0 citations · 21 references
Computer Science Mathematics

Abstract

Given a binary parity-check matrix $H$ and an integer $r$, the covering-radius decision problem asks whether every attainable syndrome can be represented by an error vector of Hamming weight at most $r$. We study this problem for sparse parity-check matrices with bounded row and column weights. Using a bounded-occurrence quantified-SAT reduction, we prove that the problem is $\Pi_2^{\mathrm P}$-complete for matrices with maximum row and column weight three, and remains $\Pi_2^{\mathrm P}$-hard under a constant multiplicative gap. Starting from Vertex Cover on 3-regular graphs, we also obtain an explicit NP-hard approximation factor under the same weight constraints. We remark that weight three is the exact threshold for hardness: if either the maximum row weight or the maximum column weight is at most two, the covering radius can be computed in polynomial time.

View source

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.