Austrin, Per ;
Kaski, Petteri ;
Koivisto, Mikko ;
Nederlof, Jesper
Dense Subset Sum May Be the Hardest
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^*(2^{n/2})time algorithm for SUBSET SUM by Horowitz and Sahni [J. ACM 1974] can be beaten in the worstcase setting by a "truly faster", O^*(2^{(0.5delta)*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.5epsilon)*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.
BibTeX  Entry
@InProceedings{austrin_et_al:LIPIcs:2016:5714,
author = {Per Austrin and Petteri Kaski and Mikko Koivisto and Jesper Nederlof},
title = {{Dense Subset Sum May Be the Hardest}},
booktitle = {33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
pages = {13:113:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770019},
ISSN = {18688969},
year = {2016},
volume = {47},
editor = {Nicolas Ollinger and Heribert Vollmer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5714},
URN = {urn:nbn:de:0030drops57143},
doi = {10.4230/LIPIcs.STACS.2016.13},
annote = {Keywords: subset sum, additive combinatorics, exponentialtime algorithm, homomorphic hashing, littlewood–offord problem}
}
2016
Keywords: 

subset sum, additive combinatorics, exponentialtime algorithm, homomorphic hashing, littlewood–offord problem 
Seminar: 

33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)

Issue date: 

2016 
Date of publication: 

2016 