computational complexity 1ldpc codes 1minimum distance 1np-completeness 1parameterized complexity 1regular Tanner graphs 1
From the 1 of 3 linked papers with an AI index.
3 papers
cs.CC2026
On the Intractability of the Minimum Distance Problem for Regular LDPC Codes
Chenyuan Jia, Qingqing Peng, Ke Liu +2
The paper investigates the computational difficulty of determining the minimum distance of regular LDPC codes, proving NP‑completeness and W[1]‑completeness for various left‑regula…
cs.LG2026
SFT Overtraining Predicts Rank Inversion via Entropy Collapse Under RLVR
Siddharth Aphale, Kelly Liu
The standard heuristic of selecting the SFT checkpoint with the highest pass@1 for GRPO can fail when SFT compresses the rollout distribution. For binary rewards, the expected with…
cs.IT2026
Linear Complexity Computation of Code Distance and Minimum Size of Trapping Sets for LDPC Codes with Bounded Treewidth
Qingqing Peng, Ke Liu, Guiying Yan +1
It is well known that, given \(b\ge 0\), finding an -trapping set with the minimum \(a\) in a binary linear code is NP-hard. In this paper, we demonstrate that this problem…