DROPS

Document

APPROX

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.10

Hardness of the Binary Covering Radius Problem in Large 𝓁_p Norms

Authors: Huck Bennett and Peter Ly

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract

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.

Cite as

Huck Bennett and Peter Ly. Hardness of the Binary Covering Radius Problem in Large 𝓁_p Norms. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bennett_et_al:LIPIcs.APPROX/RANDOM.2026.10,
  author =	{Bennett, Huck and Ly, Peter},
  title =	{{Hardness of the Binary Covering Radius Problem in Large 𝓁\underlinep Norms}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{10:1--10:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.10},
  URN =		{urn:nbn:de:0030-drops-277274},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.10},
  annote =	{Keywords: Covering radius problem, linear discrepancy, hardness of approximation}
}

Search Results

Documents authored by Ly, Peter

Hardness of the Binary Covering Radius Problem in Large 𝓁_p Norms

Abstract

Cite as

Thanks for your feedback!

Could not send message