Subset sum in the absence of concentration

P. Austrin, P. Kaski, M. Koivisto, J. Nederlof

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

14 Citations (Scopus)
117 Downloads (Pure)

Abstract

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(2^0.3399nB^4) 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. eywords: subset sum, additive combinatorics, exponential-time algorithm, homomorphic hashing, Littlewood--Offord problem
Original languageEnglish
Title of host publication32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015, München., Germany, March 4-7, 2015)
EditorsE.W. Mayr, N. Ollinger
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages48-61
ISBN (Print)978-3-939897-78-1
DOIs
Publication statusPublished - 2015
Event32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) - Technische Universität München, München, Germany
Duration: 4 Mar 20157 Mar 2015
Conference number: 32
http://wwwmayr.in.tum.de/konferenzen/STACS2015/

Publication series

NameLIPIcs: Leibniz International Proceedings in Informatics
Volume30
ISSN (Print)1868-8968

Conference

Conference32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Abbreviated titleSTACS 2015
CountryGermany
City München
Period4/03/157/03/15
Internet address

Fingerprint

Dive into the research topics of 'Subset sum in the absence of concentration'. Together they form a unique fingerprint.

Cite this