Subset Balancing and Generalized Subset Sum via Lattices
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917432371707904 |
|---|---|
| author | Gao, Yiming Feng, Yansong Hu, Honggang Pan, Yanbin |
| author_facet | Gao, Yiming Feng, Yansong Hu, Honggang Pan, Yanbin |
| contents | 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ę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π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 = τ$. 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πe})^n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_04656 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Subset Balancing and Generalized Subset Sum via Lattices Gao, Yiming Feng, Yansong Hu, Honggang Pan, Yanbin Data Structures and Algorithms Computational Complexity 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ę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π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 = τ$. 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πe})^n)$. |
| title | Subset Balancing and Generalized Subset Sum via Lattices |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2604.04656 |