Change search
ReferencesLink to record
Permanent link

Direct link
Dense Subset Sum may be the hardest
KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
2016 (English)In: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2016Conference paper (Refereed)Text
Abstract [en]

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∗(2n/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-δ)n)-time algorithm, with some constant δ > 0. Continuing an earlier work [STACS 2015], we study Subset Sum parameterized by the maximum bin size β, defined as the largest number of subsets of the n input integers that yield the same sum. For every ∈ > 0 we give a truly faster algorithm for instances with β ≤ 2(0.5-∈)n, as well as instances with β ≥ 20.661n. Consequently, we also obtain a characterization in terms of the popular density parameter n/log2 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.

Place, publisher, year, edition, pages
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2016.
Keyword [en]
Additive combinatorics, Exponential-time algorithm, Homomorphic hashing, Littlewood-offord problem, Subset Sum
National Category
Discrete Mathematics
Identifiers
URN: urn:nbn:se:kth:diva-188298DOI: 10.4230/LIPIcs.STACS.2016.13ScopusID: 2-s2.0-84961625723ISBN: 9783959770019OAI: oai:DiVA.org:kth-188298DiVA: diva2:936276
Conference
33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, 17 February 2016 through 20 February 2016
Funder
Swedish Research Council Formas, 621-2012-4546
Note

QC 20160613

Available from: 2016-06-13 Created: 2016-06-09 Last updated: 2016-06-13Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Austrin, Per
By organisation
Theoretical Computer Science, TCS
Discrete Mathematics

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 13 hits
ReferencesLink to record
Permanent link

Direct link