Subset Balancing and Generalized Subset Sum via Lattices
Pith reviewed 2026-05-10 19:41 UTC · model grok-4.3
The pith
Subset balancing with bounded coefficients reduces directly to one infinity-norm shortest-vector instance in dimension n+1.
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
We give a reduction from Subset Balancing with C = {-d, …, d} to a single instance of SVP_∞ in dimension n+1. Instantiating this reduction with the best known ℓ_∞-SVP algorithms yields a deterministic Õ((6√(2πe))^n)-time algorithm and a randomized Õ(2^{2.443n})-time algorithm. The exponent depends only on n, improving on meet-in-the-middle for all d ≥ 15. For sufficiently large d we also obtain a polynomial-time algorithm. The reduction extends from the box constraint [-d,d]^n to any centrally symmetric convex body K ⊆ R^n, giving deterministic time Õ(2^{c_K n}) for a constant c_K depending only on the shape of K. We further reduce the worst-case Generalized Subset Sum problem to CVP_∞ in n+
What carries the argument
A single lattice in dimension n+1 whose shortest nonzero vector in the infinity norm is exactly a nonzero balancing vector c ∈ C^n satisfying c · x = 0.
If this is right
- For every d ≥ 15 the problem is solvable faster than the meet-in-the-middle algorithm whose time grows with |C|^{n/2}.
- When d is large enough the problem admits a polynomial-time algorithm.
- Generalized Subset Sum reduces to a single CVP_∞ instance whose distances are integers, so an approximate CVP oracle still works.
- In the average case the CVP instance satisfies a bounded-distance promise with high probability, removing the log-log d factor.
- The same reduction works for any centrally symmetric convex body K in place of the box [-d,d]^n.
Where Pith is reading between the lines
- The same lattice embedding may let other bounded-coefficient search problems be attacked with lattice algorithms whose exponents are independent of the coefficient range.
- Average-case improvements suggest that random instances of these problems may be easier than worst-case instances in a lattice-geometric sense.
- Because the construction is deterministic and works for every x, it immediately yields worst-case algorithms for related problems such as the unbounded knapsack decision version.
Load-bearing premise
The shortest nonzero vector of the constructed lattice in infinity norm must encode a valid nonzero coefficient vector c for every input x and every d.
What would settle it
A concrete vector x ∈ Z^n and bound d such that the shortest nonzero lattice vector in infinity norm does not satisfy both c · x = 0 and c_i ∈ {-d, …, d} for all i.
read the original abstract
We study the Subset Balancing problem: given $x \in \mathbb{Z}^n$ and a coefficient set $C \subseteq \mathbb{Z}$, find a nonzero vector $c \in C^n$ such that $c\cdot x = 0$. The standard meet-in-the-middle algorithm runs in time $\tilde{O}(|C|^{n/2})$, and recent improvements (SODA 2022, Chen, Jin, Randolph, and Servedio; STOC 2026, Randolph and W\k{e}grzycki) beyond this barrier apply mainly when $d$ is constant. We give a reduction from Subset Balancing with $C = \{-d, \dots, d\}$ to a single instance of SVP$_{\infty}$ in dimension $n+1$. Instantiating this reduction with the best known $\ell_\infty$-SVP algorithms yields a deterministic $\tilde{O}((6\sqrt{2\pi e})^n)$-time algorithm and a randomized $\tilde{O}(2^{2.443n})$-time algorithm. The exponent depends only on $n$, improving on meet-in-the-middle for all $d\ge 15$. For sufficiently large $d$ we also obtain a polynomial-time algorithm. The reduction extends from the box constraint $[-d,d]^n$ to any centrally symmetric convex body $K\subseteq\mathbb{R}^n$, giving deterministic time $\tilde{O}(2^{c_K n})$ for a constant $c_K$ depending only on the shape of $K$. We further study the Generalized Subset Sum problem of finding $c \in C^n$ such that $c \cdot x = \tau$. For $C = \{-d, \dots, d\}$ or $C = \{-d,\dots,d\}\setminus\{0\}$, we reduce the worst-case problem to CVP$_{\infty}$ in dimension $n+1$. We observe that distances in our lattice take only integer values, so an approximate CVP$_{\infty}$ oracle still suffices, yielding a deterministic worst-case algorithm running in time $2^{O(n\log\log d)}$. In the average-case setting, we demonstrate that for both coefficient sets the embedded CVP$_{\infty}$ instance satisfies a bounded-distance promise with high probability, removing the $\log\log d$ factor altogether and obtaining a deterministic algorithm running in time $\tilde{O}((18\sqrt{2\pi e})^n)$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The manuscript claims a reduction from Subset Balancing (nonzero c ∈ {-d,…,d}^n with c·x=0) to a single SVP_∞ instance in dimension n+1. Instantiating with known ℓ_∞-SVP solvers yields deterministic Õ((6√(2πe))^n) and randomized Õ(2^{2.443n}) algorithms whose exponents depend only on n, improving meet-in-the-middle for d≥15; for large d a polynomial-time algorithm is obtained. The reduction generalizes to any centrally symmetric convex body K, and a parallel reduction from Generalized Subset Sum to CVP_∞ is given, with both worst-case 2^{O(n log log d)} and average-case Õ((18√(2πe))^n) bounds.
Significance. If the reduction is correct, the work is significant: it supplies a clean, parameter-free lattice embedding that lets existing SVP/CVP algorithms solve subset-balancing variants with n-only exponents and yields the first polynomial-time regime for large d. The convex-body generalization and the integer-distance observation enabling approximate CVP are additional strengths. The paper ships an explicit reduction without fitted parameters or self-referential running-time claims.
major comments (2)
- [§3] §3 (Lattice Construction for Subset Balancing): the proof that the shortest nonzero ∞-norm vector in the (n+1)-dimensional lattice is attained precisely by a vector whose first n coordinates form a valid nonzero c ∈ {-d,…,d}^n with c·x=0 must hold for arbitrary integer x, with no shorter spurious vectors permitted by coefficients outside [-d,d] or nonzero dot product. This equivalence is load-bearing for all claimed time bounds.
- [Theorem 5.3] Theorem 5.3 (Polynomial-time regime for large d): the argument that the SVP_∞ solver becomes polynomial once d exceeds a threshold must be made fully explicit, including the precise dependence of the lattice basis entries on d and the point at which the ∞-norm gap forces the shortest vector to be the desired balancing vector.
minor comments (2)
- [Abstract] Abstract: the citation 'Węgrzycki' contains a LaTeX encoding artifact; render the name correctly in the final version.
- [§2] §2 (Preliminaries): the notation for the infinity norm and the precise definition of the embedded lattice basis matrix should be cross-referenced to the construction in §3 to avoid any ambiguity in the scaling factor.
Simulated Author's Rebuttal
We thank the referee for their careful reading of the manuscript and for the positive assessment of the lattice reduction and its consequences. We address the two major comments below and will incorporate the suggested clarifications into the revised version.
read point-by-point responses
-
Referee: [§3] §3 (Lattice Construction for Subset Balancing): the proof that the shortest nonzero ∞-norm vector in the (n+1)-dimensional lattice is attained precisely by a vector whose first n coordinates form a valid nonzero c ∈ {-d,…,d}^n with c·x=0 must hold for arbitrary integer x, with no shorter spurious vectors permitted by coefficients outside [-d,d] or nonzero dot product. This equivalence is load-bearing for all claimed time bounds.
Authors: We agree that establishing this equivalence for arbitrary integer linear combinations is essential. The lattice is generated by the n vectors v_i = (e_i, M x_i) with scaling M = d + 1. Any lattice vector is therefore of the form (c, M (c · x)) for some c ∈ ℤ^n. If ||(c, M (c · x))||_∞ ≤ d then necessarily |c_i| ≤ d for all i (else the first n coordinates already exceed d) and |M (c · x)| ≤ d, which forces c · x = 0 because M > d. We will add an explicit lemma in §3 isolating this argument and stating that it applies to every integer combination of the basis vectors, thereby removing any ambiguity about spurious vectors. revision: yes
-
Referee: [Theorem 5.3] Theorem 5.3 (Polynomial-time regime for large d): the argument that the SVP_∞ solver becomes polynomial once d exceeds a threshold must be made fully explicit, including the precise dependence of the lattice basis entries on d and the point at which the ∞-norm gap forces the shortest vector to be the desired balancing vector.
Authors: We accept that the current write-up of the polynomial-time regime leaves the threshold implicit. The basis matrix has entries bounded by O(d · ||x||_∞) via the scaling M = d + 1. The ∞-norm gap is exactly 1: any valid balancing vector satisfies ||v||_∞ ≤ d while any vector with nonzero dot product or a coordinate outside [-d, d] has ∞-norm at least d + 1. We will revise Theorem 5.3 to state the explicit threshold d ≥ max{||x||_∞, 1} together with the observation that, once this gap is present, the shortest nonzero lattice vector (if its norm is ≤ d) must be the desired balancing vector; this permits replacing the general exponential-time SVP_∞ routine by a direct verification that runs in time polynomial in the input size and n. revision: yes
Circularity Check
No significant circularity: novel reduction to independent SVP algorithms
full rationale
The paper defines an explicit lattice construction in dimension n+1 from the Subset Balancing instance (x, d) such that nonzero short vectors in ℓ_∞ norm are claimed to correspond to valid balancing vectors c. Running times are obtained by substituting this reduction into externally published ℓ_∞-SVP algorithms whose exponents do not depend on the present paper's construction or fitted parameters. No self-definitional step, fitted-input prediction, or load-bearing self-citation appears; the central equivalence is a direct lattice-property claim rather than a renaming or tautology. The derivation remains self-contained against external SVP benchmarks.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Standard properties of the infinity norm and lattice shortest-vector / closest-vector problems hold as stated in the literature on lattice algorithms.
Lean theorems connected to this paper
-
IndisputableMonolith/Foundation/RealityFromDistinction.leanreality_from_one_distinction unclear?
unclearRelation between the paper passage and the cited Recognition theorem.
We give a reduction from Subset Balancing with C={−d,…,d} to a single instance of SVP_∞ in dimension n+1 … construct the lattice L_{α,q} with basis B_{α,q} … L_{α,q}∩dB^{n+1}_∞ = {(0,c) | c·x=0, |c_i|≤d}
What do these tags mean?
- matches
- The paper's claim is directly supported by a theorem in the formal canon.
- supports
- The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
- extends
- The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
- uses
- The paper appears to rely on the theorem as machinery.
- contradicts
- The paper's claim conflicts with a theorem or certificate in the canon.
- unclear
- Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.
Reference graph
Works this paper leans on
-
[1]
[AM18] Divesh Aggarwal and Priyanka Mukhopadhyay. Improved algorithms for the shortest vector problem and the closest vector problem in the infinity norm. In29th International Symposium on Algorithms and Computation (ISAAC 2018), volume 123, page 35,
work page 2018
-
[2]
Average-case subset balancing problems
[CJRS22] Xi Chen, Yaonan Jin, Tim Randolph, and Rocco A Servedio. Average-case subset balancing problems. InProceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 743–778. SIAM,
work page 2022
-
[3]
[DV13] Daniel Dadush and Santosh S. Vempala. Near-optimal deterministic algorithms for volume computation via m-ellipsoids.Proceedings of the National Academy of Sciences of the United States of America (PNAS), 110(48):19237–19245, 2013.doi:10.1073/pnas.1203863110. (cit. on p. 3,
-
[4]
Equal-subset-sum faster than the meet-in-the-middle.arXiv preprint arXiv:1905.02424,
[MNP+19] Marcin Mucha, Jesper Nederlof, Jakub Pawlewicz, et al. Equal-subset-sum faster than the meet-in-the-middle.arXiv preprint arXiv:1905.02424,
-
[5]
[Muk19] Priyanka Mukhopadhyay. Faster provable sieving algorithms for the shortest vector problem and the closest vector problem on lattices inℓp norm.arXiv preprint arXiv:1907.04406,
-
[6]
arXiv preprint arXiv:2511.10823,
[RW25] TimRandolphandKarolWęgrzycki.Beatingmeet-in-the-middleforsubsetbalancingproblems. arXiv preprint arXiv:2511.10823,
-
[7]
[vEB81] Peter van Emde Boas. Another np-complete problem and the complexity of computing short vectorsinalattice.TecnicalReport,DepartmentofMathmatics,UniversityofAmsterdam,1981. (cit. on p
work page 1981
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.