2026-07-23T21:56:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5714 2024-03-06T10:36:54Z ddc:004 open_access

Dense Subset Sum May Be the Hardest Austrin, Per Kaski, Petteri Koivisto, Mikko Nederlof, Jesper subset sum additive combinatorics exponential-time algorithm homo-morphic hashing littlewood–offord problem The SUBSET SUM problem asks whether a given set of n positive integers contains a subset of elements that sum up to a given target t. It is an outstanding open question whether the O^*(2^{n/2})-time algorithm for SUBSET SUM by Horowitz and Sahni [J. ACM 1974] can be beaten in the worst-case setting by a "truly faster", O^*(2^{(0.5-delta)*n})-time algorithm, with some constant delta > 0. Continuing an earlier work [STACS 2015], we study SUBSET SUM parameterized by the maximum bin size beta, defined as the largest number of subsets of the n input integers that yield the same sum. For every epsilon > 0 we give a truly faster algorithm for instances with beta <= 2^{(0.5-epsilon)*n}, as well as instances with beta >= 2^{0.661n}. Consequently, we also obtain a characterization in terms of the popular density parameter n/log_2(t): if all instances of density at least 1.003 admit a truly faster algorithm, then so does every instance. This goes against the current intuition that instances of density 1 are the hardest, and therefore is a step toward answering the open question in the affirmative. Our results stem from a novel combinatorial analysis of mixings of earlier algorithms for SUBSET SUM and a study of an extremal question in additive combinatorics connected to the problem of Uniquely Decodable Code Pairs in information theory. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Per Austrin and Petteri Kaski and Mikko Koivisto and Jesper Nederlof 2016 Is Part Of LIPIcs, Volume 47, 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2016.13 urn:nbn:de:0030-drops-57143 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2016.13 eng https://creativecommons.org/licenses/by/3.0/legalcode