Number Balancing is as Hard as Minkowski's Theorem and Shortest Vector

Rebecca Hoberg, Harishchandra Ramadas, Thomas Rothvoss, Xin Yang

This paper, published in 2016 by researchers at the University of Washington, explores the computational complexity of a classic problem in discrete mathematics: the Number Balancing Problem (NBP). By drawing a deep connection between NBP and the geometry of numbers, the authors show that finding high-quality solutions to number balancing is essentially as difficult as solving some of the most famous hard problems in lattice theory.

TL;DR

The authors prove a bidirectional relationship between the Number Balancing Problem and Minkowski’s Theorem. They demonstrate that an algorithm capable of finding near-optimal subset-sum balances would also provide a polynomial-factor approximation for the Shortest Vector Problem (SVP), a cornerstone of modern cryptography.

What Problem Does This Paper Address?

The Number Balancing Problem (NBP) is a variation of the classic NP-complete Partition Problem. Given a set of $n$ real numbers $a_1, \dots, a_n$ in the interval $[0, 1]$, the goal is to find two disjoint subsets whose sums are as close as possible.

Mathematically, we want to find a vector of "signs" $x \in \{-1, 0, 1\}^n$ (excluding the zero vector) that minimizes the absolute value of the inner product $|\langle a, x \rangle|$.

We know from the pigeonhole principle that a solution always exists where the difference is exponentially small (roughly $O(\sqrt{n}/2^n)$). However, finding this minimum is NP-hard. For decades, the best polynomial-time approach has been the "differencing algorithm" by Karmarkar and Karp (1982), which achieves a sub-exponential error of $n^{-\Theta(\log n)}$. The gap between what we know exists and what we can actually find in polynomial time has remained a major open question.

Methods

The authors bridge this gap by relating NBP to Minkowski’s Theorem, which states that any large enough symmetric convex body must contain a non-zero integer point.

  1. From Minkowski to NBP: The authors show that if you have an "oracle" (a black-box algorithm) that can find integer points in a symmetric convex body (an approximate Minkowski oracle), you can use it to solve NBP. They construct a specific convex body—a "slab" of a hypercube—and prove that its volume is large enough to guarantee the existence of a balancing vector via Minkowski's Theorem.
  2. From NBP to Minkowski: This is the more surprising direction. The authors show that a high-quality NBP oracle can be used to find short vectors in a lattice. They use John’s Theorem to approximate any convex body with an ellipsoid and then apply LLL lattice reduction to "regularize" that ellipsoid.
  3. Recursive Self-Reduction: A key technical innovation is a recursive technique. They show how to take an NBP oracle that finds a "somewhat" balanced solution and repeatedly apply it to smaller sub-problems to eventually find an "extremely" balanced solution. This allows them to transform a standard NBP solver into a tool for finding short vectors in general lattices.

Datasets

This is a theoretical paper in computer science and mathematics. No empirical datasets or benchmarks were used for training or evaluation. The results are established through rigorous mathematical proofs.

Key Insights and Ideas

  • The Hardness Gap: The paper suggests that the difficulty of improving upon the Karmarkar-Karp algorithm is not just a lack of ingenuity, but is tied to the fundamental hardness of lattice problems like the Shortest Vector Problem (SVP).
  • Geometric Equivalence: NBP is often thought of as a purely combinatorial problem. This paper reframes it as a geometric problem: finding an integer point near a specific hyperplane within a high-dimensional cube.
  • Lattice-Based Cryptography Connection: Since many modern cryptographic schemes (like those used for post-quantum security) rely on the hardness of finding short vectors in a lattice, this paper implies that if someone found a "too good" algorithm for number balancing, it could potentially threaten those cryptosystems.

Key Results

  • Theorem 1: A $\rho$-approximation for Minkowski’s problem (finding a point in $\rho K$) yields a $\delta$-approximation for NBP, where the error $\delta$ is exponentially small: $2^{-n^{\Theta(1/\rho)}}$.
  • Theorem 3: Conversely, any polynomial-time algorithm that guarantees an NBP solution with error at most $2^{\sqrt{n}}/2^n$ would provide an $O(n^5)$-approximation for Minkowski’s problem.
  • SVP Hardness: The authors conclude that NBP is essentially as hard as the Shortest Vector Problem in the $L_\infty$ norm.

Limitations and Future Work

  • The "High Quality" Requirement: The reduction from NBP to Minkowski requires an NBP oracle with a very small error bound ($\leq 2^{\sqrt{n}}/2^n$). The paper does not definitively prove the hardness of finding "moderately" good solutions—those that are better than Karmarkar-Karp but still much larger than the pigeonhole bound.
  • Closing the Gap: A natural next step for researchers is to see if these techniques can be pushed further to show that even achieving an error of, say, $2^{-n^{0.1}}$ is as hard as lattice problems.
  • Algorithmic Improvements: While the paper focuses on hardness, the geometric insights might eventually lead to new types of approximation algorithms for NBP that use lattice-based techniques.

Summary updated

Abstract

The number balancing (NBP) problem is the following: given real numbers $a_1,\ldots,a_n \in [0,1]$, find two disjoint subsets $I_1,I_2 \subseteq [n]$ so that the difference $|\sum_{i \in I_1}a_i - \sum_{i \in I_2}a_i|$ of their sums is minimized. An application of the pigeonhole principle shows that there is always a solution where the difference is at most $O(\frac{\sqrt{n}}{2^n})$. Finding the minimum, however, is NP-hard. In polynomial time,the differencing algorithm by Karmarkar and Karp from 1982 can produce a solution with difference at most $n^{-\Theta(\log n)}$, but no further improvement has been made since then. In this paper, we show a relationship between NBP and Minkowski's Theorem. First we show that an approximate oracle for Minkowski's Theorem gives an approximate NBP oracle. Perhaps more surprisingly, we show that an approximate NBP oracle gives an approximate Minkowski oracle. In particular, we prove that any polynomial time algorithm that guarantees a solution of difference at most $2^{\sqrt{n}} / 2^{n}$ would give a polynomial approximation for Minkowski as well as a polynomial factor approximation algorithm for the Shortest Vector Problem.
BibTeX
@inproceedings{hoberg2017number,
  author = {Rebecca Hoberg and Harishchandra Ramadas and Thomas Rothvoss and Xin Yang},
  title = {{Number Balancing is as Hard as Minkowski's Theorem and Shortest Vector}},
  booktitle = {IPCO},
  year = {2017},
  url = {https://openreview.net/forum?id=9qby16kKX4},
}

Loading related content...

Figure