2026-07-26T00:33:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21092 2024-09-23T09:13:16Z ddc:004 open_access

Improved Space Bounds for Subset Sum Belova, Tatiana Chukhin, Nikolai Kulikov, Alexander S. Mihajlin, Ivan algorithms subset sum complexity space upper bounds 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 of this result is the following fine-grained lower bound: assuming that 4-SUM cannot be solved in time O(n^{2-ε}) for all ε > 0, Circuit SAT cannot be solved in time O(g2^{(1-ε)n}), for all ε > 0 (where n and g denote the number of inputs and the number of gates, respectively). 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tatiana Belova and Nikolai Chukhin and Alexander S. Kulikov and Ivan Mihajlin 2024 Is Part Of LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2024.21 urn:nbn:de:0030-drops-210925 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.21 eng https://creativecommons.org/licenses/by/4.0/legalcode