Space-efficient Las Vegas Algorithms For K-SUM

Wang Joshua. Arxiv 2013

[Paper]    
ARXIV Independent

Using hashing techniques, this paper develops a family of space-efficient Las Vegas randomized algorithms for $k$-SUM problems. This family includes an algorithm that can solve 3-SUM in $O(n^2)$ time and $O(\sqrt{n})$ space. It also establishes a new time-space upper bound for SUBSET-SUM, which can be solved by a Las Vegas algorithm in \(O^(2^{(1-\sqrt{\8/9\beta})n})\) time and \(O^(2^{\beta n})\) space, for any $\beta \in [0,\text{9}/32]$.

Similar Work

• Optimal Las Vegas Locality Sensitive Data Structures
• Asymptotic Improvement Of The Gilbert-varshamov Bound On The Size Of Binary Codes
• Approximate Nearest Neighbors In Limited Space
• De Dictionariis Dynamicis Pauco Spatio Utentibus