Publication
Improved Space Bounds for Subset Sum
ESA 2024, 2024. PDF · Official record
Abstract
More than 40 years ago, Schroeppel and Shamir presented an algorithm that solves the Subset Sum problem for \(n\) integers in time \(O^*(2^{0.5n})\) and space \(O^*(2^{0.25n})\). The time upper bound remains unbeaten, but the space upper bound has been improved to \(O^*(2^{0.249999n})\) in a recent breakthrough paper by Nederlof and Węgrzycki (STOC 2021). Their algorithm is a clever combination of a number of previously known techniques with a new reduction and a new algorithm for the Orthogonal Vectors problem.
In this paper, we give two new algorithms for Subset Sum. We start by presenting an Arthur–Merlin algorithm: upon receiving the verifier’s randomness, the prover sends an \(n/4\)-bit long proof to the verifier who checks it in deterministic time and space \(O^*(2^{n/4})\). An interesting consequence is the following fine-grained lower bound: assuming that 4-SUM cannot be solved in time \(O(n^{2-\varepsilon})\) for all \(\varepsilon>0\), Circuit SAT cannot be solved in time \(O(g2^{(1-\varepsilon)n})\) for all \(\varepsilon>0\), where \(n\) and \(g\) denote the number of inputs and gates.
Then, we improve the space bound by Nederlof and Węgrzycki to \(O^*(2^{0.246n})\) and also simplify their algorithm and its analysis. We achieve this space bound by further filtering sets of subsets using a random prime number. This allows us to reduce an instance of Subset Sum to a larger number of instances of smaller size.