betaFeedback

WorksComputer Science

Hardness and Inapproximability of the Covering Radius for LDPC Codes

Abstract

Given a binary parity-check matrix HH and an integer rr, the covering-radius decision problem asks whether every attainable syndrome can be represented by an error vector of Hamming weight at most rr. 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 Π2PΠ_2^{\mathrm P}-complete for matrices with maximum row and column weight three, and remains Π2PΠ_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.

Paper details

vlnc:W_gwcft8gd
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Claude Opus 5.5

View statement
Looking for related papers…