Document Open Access Logo

Improved Space-Time Tradeoffs for kSUM

Authors Isaac Goldstein, Moshe Lewenstein, Ely Porat

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2018.37.pdf
  • Filesize: 444 kB
  • 14 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • kSUM
  • space-time tradeoff
  • self-reduction

Metrics

Abstract

In the kSUM problem we are given an array of numbers a_1,a_2,...,a_n and we are required to determine if there are k different elements in this array such that their sum is 0. This problem is a parameterized version of the well-studied SUBSET-SUM problem, and a special case is the 3SUM problem that is extensively used for proving conditional hardness. Several works investigated the interplay between time and space in the context of SUBSET-SUM. Recently, improved time-space tradeoffs were proven for kSUM using both randomized and deterministic algorithms.
In this paper we obtain an improvement over the best known results for the time-space tradeoff for kSUM. A major ingredient in achieving these results is a general self-reduction from kSUM to mSUM where m<k, and several useful observations that enable this reduction and its implications. The main results we prove in this paper include the following: (i) The best known Las Vegas solution to kSUM running in approximately O(n^{k-delta sqrt{2k}}) time and using O(n^{delta}) space, for 0 <= delta <= 1. (ii) The best known deterministic solution to kSUM running in approximately O(n^{k-delta sqrt{k}}) time and using O(n^{delta}) space, for 0 <= delta <= 1. (iii) A space-time tradeoff for solving kSUM using O(n^{delta}) space, for delta>1. (iv) An algorithm for 6SUM running in O(n^4) time using just O(n^{2/3}) space. (v) A solution to 3SUM on random input using O(n^2) time and O(n^{1/3}) space, under the assumption of a random read-only access to random bits.

Cite As Get BibTex

Isaac Goldstein, Moshe Lewenstein, and Ely Porat. Improved Space-Time Tradeoffs for kSUM. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.37

Author Details

Isaac Goldstein
  • Bar-Ilan University, Ramat Gan, Israel
Moshe Lewenstein
  • Bar-Ilan University, Ramat Gan, Israel
Ely Porat
  • Bar-Ilan University, Ramat Gan, Israel

Funding

  • Goldstein, Isaac: This research is supported by the Adams Foundation of the Israel Academy of Sciences and Humanities.
  • Lewenstein, Moshe: This work was partially supported by an ISF grant #1278/16, BSF grant 2010437 and a GIF grant 1147/2011.
  • Porat, Ely: This work was partially supported by an ISF grant #1278/16.

References

  1. Amir Abboud and Kevin Lewi. Exact weight subgraphs and the k-sum conjecture. In International Colloquium on Automata, Languages and Programming, ICALP 2013, pages 1-12, 2013. Google Scholar
  2. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Foundations of Computer Science, FOCS 2014, pages 434-443, 2014. Google Scholar
  3. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In International Colloquium on Automata, Languages and Programming, ICALP 2014, pages 39-51, 2014. Google Scholar
  4. Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. In Symposium on Theory of Computing, STOC 2015, pages 41-50, 2015. Google Scholar
  5. Amihood Amir, Timothy M. Chan, Moshe Lewenstein, and Noa Lewenstein. On hardness of jumbled indexing. In International Colloquium on Automata, Languages and Programming, ICALP 2014, pages 114-125, 2014. Google Scholar
  6. Per Austrin, Petteri Kaski, Mikko Koivisto, and Jussi Määttä. Space-time tradeoffs for subset sum: An improved worst case algorithm. In International Colloquium on Automata, Languages, and Programming, ICALP 2013, pages 45-56, 2013. Google Scholar
  7. Nikhil Bansal, Shashwat Garg, Jesper Nederlof, and Nikhil Vyas. Faster space-efficient algorithms for subset sum and k-sum. In Symposium on Theory of Computing, STOC 2017, pages 198-209, 2017. Google Scholar
  8. Ilya Baran, Erik D. Demaine, and Mihai Patrascu. Subquadratic algorithms for 3SUM. In Workshop on Algorithms and Data Structures, WADS 2005, pages 409-421, 2005. Google Scholar
  9. Gill Barequet and Sariel Har-Peled. Polygon-containment and translational min-hausdorff-distance between segment sets are 3sum-hard. In Symposium on Discrete Algorithms, SODA 1999, pages 862-863, 1999. Google Scholar
  10. Anja Becker, Jean-Sébastien Coron, and Antoine Joux. Improved generic algorithms for hard knapsacks. In Theory and Applications of Cryptographic Techniques, EUROCRYPT 2011, pages 364-385, 2011. Google Scholar
  11. Martin Dietzfelbinger. Universal hashing and k-wise independent random variables via integer arithmetic without primes. In Symposium on Theoretical Aspects of Computer Science, STACS 1996, pages 569-580, 1996. Google Scholar
  12. Itai Dinur, Orr Dunkelman, Nathan Keller, and Adi Shamir. Efficient dissection of composite problems, with applications to cryptanalysis, knapsacks, and combinatorial search problems. In Cryptology Conference, CRYPTO 2012, pages 719-740, 2012. Google Scholar
  13. Anka Gajentaan and Mark H. Overmars. On a class of O(n²) problems in computational geometry. Comput. Geom., 5:165-185, 1995. Google Scholar
  14. Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat. How hard is it to find (honest) witnesses? In European Symposium on Algorithms, ESA 2016, pages 45:1-45:16, 2016. Google Scholar
  15. Isaac Goldstein, Tsvi Kopelowitz, Moshe Lewenstein, and Ely Porat. Conditional lower bounds for space/time tradeoffs. In Algorithms and Data Structures Symposium, WADS 2017, pages 421-436, 2017. Google Scholar
  16. Isaac Goldstein, Moshe Lewenstein, and Ely Porat. Orthogonal vectors indexing. In International Symposium on Algorithms and Computation, ISAAC 2017, pages 40:1-40:12, 2017. Google Scholar
  17. Nick Howgrave-Graham and Antoine Joux. New generic algorithms for hard knapsacks. In Theory and Applications of Cryptographic Techniques, EUROCRYPT 2010, pages 235-256, 2010. Google Scholar
  18. Richard M. Karp. Reducibility among combinatorial problems. In Symposium on the Complexity of Computer Computations, pages 85-103, 1972. Google Scholar
  19. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3SUM conjecture. In Symposium on Discrete Algorithms, SODA 2016, pages 1272-1287, 2016. Google Scholar
  20. Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, and R. Ryan Williams. Deterministic time-space trade-offs for k-sum. In International Colloquium on Automata, Languages, and Programming, ICALP 2016, pages 58:1-58:14, 2016. Google Scholar
  21. Mihai Patrascu. Towards polynomial lower bounds for dynamic problems. In Symposium on Theory of Computing, STOC 2010, pages 603-610, 2010. Google Scholar
  22. Mihai Patrascu and Ryan Williams. On the possibility of faster SAT algorithms. In Symposium on Discrete Algorithms, SODA 2010, pages 1065-1075, 2010. Google Scholar
  23. Richard Schroeppel and Adi Shamir. A T s^2 = o(2^n) time/space tradeoff for certain np-complete problems. In Foundations of Computer Science, FOCS 1979, pages 328-336, 1979. Google Scholar
  24. Joshua R. Wang. Space-efficient randomized algorithms for K-SUM. In European Symposium on Algorithms, ESA 2014, pages 810-829, 2014. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact