Hardness of the Binary Covering Radius Problem in Large $\ell_p$ Norms

This paper establishes the first explicit $\mathsf{NP}$-hardness results for the approximate Covering Radius Problem on lattices in $\ell_p$ norms for sufficiently large $p$ (specifically $p > 35.31$), proving that the problem remains hard even for approximation factors approaching $9/8$as$p$ tends to infinity.

The Gist

Imagine you are a city planner trying to design a new neighborhood. You have a grid of streets (the lattice), and you want to make sure that no matter where a person drops a ball in the city, they are never too far from a street corner (a lattice point).

The Covering Radius Problem is essentially asking: "What is the worst-case distance a person could be from the nearest street corner?" If you can solve this perfectly, you know exactly how big your "safety net" needs to be.

For decades, computer scientists have been trying to figure out how hard it is to calculate this distance, especially when we only need a "good enough" answer (an approximation) rather than a perfect one. While we know it's very hard for some types of grids, for the standard "straight-line" distance (the $\ell_2$ norm, or Euclidean distance), we didn't even know if it was hard to approximate.

This paper, written by Huck Bennett and Peter Ly, is a breakthrough. They prove that for a specific type of grid measurement (using a "large" distance metric called $\ell_p$ where $p$ is a big number), figuring out the covering radius is computationally impossible to solve efficiently.

Here is the breakdown using simple analogies:

1. The Game: "Find the Farthest Point"

Imagine a giant, invisible net made of strings (the lattice). You drop a ball anywhere in the room.

• The Goal: Find the spot in the room where the ball is furthest from any string.
• The Hard Part: The room is infinite, and the strings are arranged in a complex, repeating pattern.
• The Question: Is there a fast computer program that can tell us, "Yes, the furthest point is within 1 meter," or "No, there is a point 10 meters away"?

2. The "Binary" Twist

The authors didn't just look at the standard problem. They created a slightly different version called the Binary Covering Radius Problem.

• Standard Version: You can move the ball to any integer coordinate to find the closest string.
• Binary Version: You are only allowed to move the ball to coordinates that are either 0 or 1 (like a light switch: off or on).
• Why this matters: It turns out that if you can't solve the "Binary" version easily, you definitely can't solve the standard version easily. It's like saying, "If you can't find the exit in a maze when you can only turn left or right, you certainly can't find it if you can walk in any direction."

3. The "Magic" Gadget (The Secret Sauce)

To prove the problem is hard, the authors used a clever trick involving a "gadget" (a small, pre-built puzzle piece).

• Think of this gadget as a special lock.
• They took a famous hard logic puzzle (called NAE-3-SAT, which is like a complex Sudoku where you have to ensure no row is all "True" or all "False") and turned it into a grid of numbers.
• They built a specific matrix (a grid of numbers) that acts like a translator.
  • If the logic puzzle has a solution, the "farthest point" in the grid is close to a street corner (easy to cover).
  • If the logic puzzle has no solution, the "farthest point" is very far away (hard to cover).

4. The Big Discovery: The "9/8" Barrier

The authors discovered a specific threshold.

• They found that for distance measurements where $p$ is large (roughly greater than 35), it is NP-hard to approximate the covering radius within a factor of about 1.125 (which is $9/8$).
• What does this mean? It means that if you want to know if the furthest point is within 1 meter, and you settle for an answer that says "it's within 1.125 meters," a computer still cannot do this quickly. The problem is fundamentally broken for efficient computers.
• Even more impressively, for the "infinity" distance (where you care about the single worst dimension, like the height of a building), they proved it's even harder (a complexity class called $\Pi_2$-hard), meaning it's likely impossible to solve even with very powerful theoretical computers.

5. Why Should You Care?

You might ask, "Who cares about math grids?"

• Cryptography: Many modern encryption methods (the kind that will protect your bank account in the future) rely on the fact that these lattice problems are hard to solve. If someone found a fast way to solve them, they could break the encryption. This paper tells us that for certain types of these problems, we can be very confident they are safe.
• Computer Science: It solves a 20-year-old mystery. Before this, we knew these problems were hard for some weird, undefined distances, but we didn't know if they were hard for the standard, well-defined distances we actually use. Now we know they are.

Summary

The authors took a complex math problem about finding the "worst-case distance" in a grid, added a "binary switch" constraint, and proved that for large distance metrics, no computer can efficiently solve it. They did this by turning a logic puzzle into a geometric grid, showing that solving the grid is just as hard as solving the logic puzzle.

It's like proving that if you can't quickly solve a specific type of Sudoku, you also can't quickly find the best parking spot in a massive, infinite parking lot. And for this specific type of parking lot, the answer is a resounding "No, you can't."

Technical Summary

Here is a detailed technical summary of the paper "Hardness of the Binary Covering Radius Problem in Large $\ell_p$ Norms" by Huck Bennett and Peter Ly.

1. Problem Definition and Context

The paper investigates the computational hardness of the Covering Radius Problem (CRP) on lattices.

• Covering Radius ($\mu(L)$): For a lattice $L$, this is the maximum distance from any point in the span of $L$ to the nearest lattice vector.
• GapCRP: The decisional version where one must distinguish between a lattice with covering radius $\le r$ (YES) and $> \gamma r$ (NO).
• Current State of Knowledge:
  • For the Shortest Vector Problem (GapSVP), NP-hardness is known for any constant approximation factor $\gamma \ge 1$ in any $\ell_p$ norm.
  • For GapCRP, hardness is poorly understood. While $\Pi_2$-hardness (a higher complexity class than NP) was shown for large, non-explicit $p$ and $p=\infty$ by Haviv and Regev (2006), it was unknown if GapCRP was NP-hard for any explicit, finite $p$.
  • The exact GapCRP in $\ell_2$ is not even known to be NP-hard.

The Binary Covering Radius Problem (BinGapCRP):
The authors introduce a variant called BinGapCRP.

• YES Instance: The linear discrepancy is small (every vector in the fundamental parallelepiped is close to a lattice vector with binary coefficients $x \in \{0,1\}^n$).
• NO Instance: The covering radius is large (there exists a vector far from any lattice vector $x \in \mathbb{Z}^n$).
• Significance: BinGapCRP trivially reduces to both standard GapCRP and the Linear Discrepancy Problem (LinDisc) in an approximation-preserving way. Proving hardness for BinGapCRP implies hardness for the others.

2. Methodology

The authors adapt and extend the hardness reduction machinery from Manurangsi (2021), who proved $\Pi_2$-hardness for $(9/8 - \epsilon)$-LinDisc in the $\ell_\infty$ norm.

Core Reduction Strategy

The reduction is from the Not-All-Equal 3-SAT (NAE-E3-SAT) problem, specifically a variant with perfect completeness and high soundness.

1. Source Problem: $(15/16 + \epsilon, 1)$-NAE-E3-SAT. The authors establish (via folklore arguments and Section A) that distinguishing between formulas where all constraints are satisfiable vs. at most $15/16$ are satisfiable is NP-hard.
2. Construction: Given a NAE-E3-SAT formula $\phi$, they construct a matrix $A$ (the basis for the lattice) composed of:
   • The incidence matrix $B$ of the formula (scaled by $1/3$).
   • A "gadget" matrix $G$ (a $3 \times 3$matrix with entries$\pm 1$) tensored with a diagonal matrix$D_p$ that accounts for variable degrees.
     $$A = \begin{pmatrix} \frac{1}{3}B \\ \frac{1}{3}B \\ \frac{1}{3}B \\ G \otimes D_p \end{pmatrix}$$
3. Key Technical Modifications for $\ell_p$ Norms:
   • Gadget Analysis: They extend Manurangsi's analysis of the gadget matrix $G$ from $\ell_\infty$ to general $\ell_p$ norms. They prove that for any $u \in [0,1]^3$, there exists a binary $z$ such that $\|G(u-z)\|_p$ is small, but if $u$ is far from binary, the distance is large.
   • Degree Scaling: They introduce the diagonal matrix $D_p = \text{diag}(\deg(v_i)^{1/p})$ to balance the contributions of variables appearing in different numbers of constraints, ensuring the $\ell_p$ norm behaves correctly during the reduction.
   • Completeness vs. Soundness:
     • Completeness: If $\phi$ is satisfiable, there exists a binary vector $x$ such that $\|A(w-x)\|_p$ is small (bounded by $r$).
     • Soundness: If $\phi$ is unsatisfiable, then for any integer vector $y \in \mathbb{Z}^n$ (not just binary), $\|A(w-y)\|_p$ is large. This is the crucial step that elevates the problem from LinDisc (binary coefficients) to GapCRP (integer coefficients).

3. Key Contributions and Results

A. NP-Hardness for Explicit Finite $p$

The primary contribution is the first proof of NP-hardness for GapCRP in explicit, finite $\ell_p$ norms.

• Theorem 1.1: For any $p > p_0 \approx 35.31$, the problem $(\gamma(p) - \epsilon)$-BinGapCRP$_p$ is NP-hard.
• Approximation Factor: The factor $\gamma(p)$ is given explicitly by:
  $$\gamma(p) = \left( \frac{9^p + 159 \cdot 3^p}{8^{p+2} + 96 \cdot 6^p} \right)^{1/p}$$
• Asymptotic Behavior: As $p \to \infty$, $\gamma(p) \to 9/8$.
• Significance: This resolves the open question of whether GapCRP is hard for any explicit finite $p$. Previously, only non-explicit large $p$ were known to be hard.

B. $\Pi_2$-Hardness in $\ell_\infty$

The authors strengthen previous results regarding the $\ell_\infty$ norm.

• Theorem 1.2: $(9/8 - \epsilon)$-BinGapCRP$_\infty$ is $\Pi_2$-hard.
• Implication: This implies $(9/8 - \epsilon)$-GapCRP$_\infty$ is $\Pi_2$-hard. This improves upon the approximation factor of the earlier Haviv-Regev result (which was $3/2$) and extends Manurangsi's LinDisc result to the full Covering Radius problem.

C. Connection to Linear Discrepancy

The work demonstrates that the hardness of the Linear Discrepancy Problem (LinDisc) in $\ell_p$ norms (previously unstudied for finite $p$) is equivalent to the hardness of the Binary Covering Radius Problem.

4. Significance and Impact

1. Bridging the Gap: The paper closes a 20-year gap in lattice complexity theory (since Haviv and Regev 2006) by providing the first explicit hardness results for GapCRP in finite dimensions.
2. Cryptographic Relevance: The Covering Radius Problem is a foundational worst-case problem for lattice-based cryptography (e.g., reductions to average-case problems like Learning With Errors). Understanding its hardness thresholds is critical for assessing the security of cryptographic schemes.
3. Refining Complexity Classes: The distinction between NP-hardness (for $p > 35.31$) and $\Pi_2$-hardness (for $p=\infty$) provides a more nuanced map of the complexity landscape of lattice problems. It suggests that while GapCRP is likely hard for all $p$, the nature of the hardness may shift as $p$ increases.
4. Methodological Advancement: The technique of adapting the "gadget" reduction from $\ell_\infty$ to $\ell_p$ via degree-weighted scaling offers a new toolkit for analyzing lattice problems in general norms.

5. Open Questions

The authors highlight that the most significant open question remains: Is exact GapCRP in $\ell_2$ NP-hard?
While their results show hardness for large $p$, the case of $p=2$ (Euclidean norm) is the most relevant for practical applications and cryptography, yet its hardness remains unproven. Additionally, it is unknown if an Arthur-Merlin (AM) protocol exists for LinDisc similar to the one for GapCRP, which would place limits on its hardness.