2026-09-10T09:44:54Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:27727 2026-09-09T12:19:35Z ddc:004 open_access
Hardness of the Binary Covering Radius Problem in Large 𝓁_p Norms Bennett, Huck Ly, Peter Covering radius problem linear discrepancy hardness of approximation We study the hardness of the Ξ³-approximate decisional Covering Radius Problem on lattices in the 𝓁_p norm (Ξ³-GapCRP_p). Specifically, we prove that there is an explicit function Ξ³(p), with Ξ³(p) > 1 for p > pβ‚€ β‰ˆ 35.31 and lim_{p β†’ ∞} Ξ³(p) = 9/8, such that for any constant Ξ΅ > 0, (Ξ³(p)-Ξ΅)-GapCRP_p is NP-hard. This shows the first hardness of GapCRP_p for explicit p < ∞. Work of Haviv and Regev (CCC, 2006 and CJTCS, 2012) previously showed Ξ β‚‚-hardness of approximation for GapCRP_p for all sufficiently large (but non-explicit) finite p and for p = ∞. In fact, our hardness results hold for a variant of GapCRP called the Binary Covering Radius Problem (BinGapCRP). The Binary Covering Radius Problem trivially reduces to both GapCRP and the decisional Linear Discrepancy Problem (LinDisc) in any norm in an approximation-preserving way. We also show Ξ β‚‚-hardness of (9/8 - Ξ΅)-BinGapCRP in the 𝓁_∞ norm for any constant Ξ΅ > 0. Our work extends and heavily uses the work of Manurangsi (IPL, 2021), which showed Ξ β‚‚-hardness of (9/8 - Ξ΅)-LinDisc in the 𝓁_∞ norm. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Huck Bennett and Peter Ly 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.10 urn:nbn:de:0030-drops-277274 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.10 eng https://creativecommons.org/licenses/by/4.0/legalcode