Subset sum in the absence of concentration
2015 (English)In: Leibniz International Proceedings in Informatics, LIPIcs, 2015, 48-61 p.Conference paper (Refereed)
We study the exact time complexity of the Subset Sum problem. Our focus is on instances that lack additive structure in the sense that the sums one can form from the subsets of the given integers are not strongly concentrated on any particular integer value. We present a randomized algorithm that runs in O (20.3399nB4) time on instances with the property that no value can arise as a sum of more than B different subsets of the n given integers.
Place, publisher, year, edition, pages
2015. 48-61 p.
Additive combinatorics, Exponential-time algorithm, Homomorphic hashing, Littlewood-Offord problem, Subset sum, Exponential time algorithm, Set theory
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-167392DOI: 10.4230/LIPIcs.STACS.2015.48ScopusID: 2-s2.0-84923924069ISBN: 9783939897781OAI: oai:DiVA.org:kth-167392DiVA: diva2:814485
32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, 4 March 2015 through 7 March 2015
FunderSwedish Research Council, 621-2012-4546
QC 201505272015-05-272015-05-222015-05-27Bibliographically approved