## Dense Subset Sum may be the hardest

Loading...

##### Journal Title

##### Journal ISSN

##### Volume Title

Conference article in proceedings

This publication is imported from Aalto University research portal.

View publication in the Research portal

View/Open full text file from the Research portal

Other link related to publication

View publication in the Research portal

View/Open full text file from the Research portal

Other link related to publication

##### Date

2016-02-01

##### Major/Subject

##### Mcode

##### Degree programme

##### Language

en

##### Pages

1-12

##### Series

Leibniz International Proceedings in Informatics, Volume 47

##### Abstract

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.##### Description

##### Keywords

Additive combinatorics, Exponential-time algorithm, Homomorphic hashing, Littlewood-offord problem, Subset Sum

##### Other note

##### Citation

Austrin , P , Kaski , P , Koivisto , M & Nederlof , J 2016 , Dense Subset Sum may be the hardest . in N Ollinger & H Vollmer (eds) , Leibniz International Proceedings in Informatics : LIPIcs . vol. 47 , 13 , Schloss Dagstuhl - Leibniz-Zentrum für Informatik , pp. 1-12 , Symposium on Theoretical Aspects of Computer Science , Orleans , France , 17/02/2016 . https://doi.org/10.4230/LIPIcs.STACS.2016.13