Paper Info
Title
Space-Efficient Randomized Algorithms for K-SUM.
Abstract
Recent results by Dinur et al. (2012) on random SUBSETSUM instances and by Austrin et al. (2013) on worst-case SUBSETSUM instances have improved the long-standing time-space tradeoff curve. We analyze a family of hash functions previously introduced by Dietzfel-binger (1996), and apply it to decompose arbitrary k-Sum instances into smaller ones. This allows us to extend the aforementioned tradeoff curve to the k-Sum problem, which is SubsetSum restricted to sets of size k. Three consequences are: a Las Vegas algorithm solving 3-Sum in O(n(2)) time and (O) over tilde(root n) space, a Monte Carlo algorithm solving k-Sum in (O) over tilde (n(k-root 2k+1)) time and (O) over tilde (n) space for k >= 3, and a Monte Carlo algorithm solving k-Sum in (O) over tilde (n(k-delta(k-1)) + n(k-1-delta(root 2k-2))) time and (O) over tilde (n(delta)) space, for delta is an element of [0, 1] and k >= 3.
Year
Venue
Keywords
2014
ALGORITHMS - ESA 2014
k-sum,subset-sum,hashing,time-space tradeoffs
Field
DocType
Volume
Randomized algorithm,Discrete mathematics,Subset sum problem,Combinatorics,Monte Carlo algorithm,Hash function,Las Vegas algorithm,Mathematics
Conference
8737
ISSN
Citations 
PageRank 
0302-9743
1
0.35
References 
Authors
7
1
Name
Order
Citations
PageRank
Joshua R. Wang1695.83