Space-efficient Las Vegas Algorithms For K-SUM
Wang Joshua. Arxiv 2013
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, \9/32]\).
Similar Work