Back to Search
Start Over
Dense subset sum may be the hardest
- Source :
- 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, 13:1-13:14, STARTPAGE=13:1;ENDPAGE=13:14;TITLE=33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France
- Publication Year :
- 2016
-
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 worst-case setting by a "truly faster", $O^*(2^{(0.5-\delta)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 \leq 2^{(0.5-\epsilon)n}$, as well as instances with $\beta \geq 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 novel combinations 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.<br />Comment: 14 pages
- Subjects :
- FOS: Computer and information sciences
Additive combinatorics
Discrete Mathematics (cs.DM)
Computer Science - Information Theory
cs.DM
0102 computer and information sciences
02 engineering and technology
Computational Complexity (cs.CC)
01 natural sciences
cs.IT
Computer Science - Data Structures and Algorithms
0202 electrical engineering, electronic engineering, information engineering
Data Structures and Algorithms (cs.DS)
math.IT
ta113
000 Computer science, knowledge, general works
cs.CC
Information Theory (cs.IT)
Subset Sum
Computer Science - Computational Complexity
cs.DS
Exponential-time algorithm
010201 computation theory & mathematics
Computer Science
Littlewood-offord problem
020201 artificial intelligence & image processing
Homomorphic hashing
Computer Science - Discrete Mathematics
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, 13:1-13:14, STARTPAGE=13:1;ENDPAGE=13:14;TITLE=33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France
- Accession number :
- edsair.doi.dedup.....e4f1f2aca007a9689edb78b54c10f3ea