Document Open Access Logo

Deterministic Time-Space Trade-Offs for k-SUM

Authors Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, R. Ryan Williams

PDF

File

Thumbnail PDF
PDF
LIPIcs.ICALP.2016.58.pdf
  • Filesize: 0.5 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • 3SUM
  • kSUM
  • time-space tradeoff
  • algorithm

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Given a set of numbers, the k-SUM problem asks for a subset of k numbers that sums to zero. When the numbers are integers, the time and space complexity of k-SUM is generally studied in the word-RAM model; when the numbers are reals, the complexity is studied in the real-RAM model, and space is measured by the number of reals held in memory at any point. We present a time and space efficient deterministic self-reduction for the k-SUM problem which holds for both models, and has many interesting consequences. To illustrate:

- 3-SUM is in deterministic time O(n^2*lg(lg(n))/lg(n)) and space O(sqrt(n*lg(n)/lg(lg(n)))). In general, any polylogarithmic-time improvement over quadratic time for 3-SUM can be converted into an algorithm with an identical time improvement but low space complexity as well.

- 3-SUM is in deterministic time O(n^2) and space O(sqrt(n)), derandomizing an algorithm of Wang.

- A popular conjecture states that 3-SUM requires n^{2-o(1)} time on the word-RAM. We show that the 3-SUM Conjecture is in fact equivalent to the (seemingly weaker) conjecture that every O(n^{.51})-space algorithm for 3-SUM requires at least n^{2-o(1)} time on the word-RAM.

- For k >= 4, k-SUM is in deterministic O(n^{k-2+2/k}) time and O(sqrt(n)) space.

Cite As Get BibTex

Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, and R. Ryan Williams. Deterministic Time-Space Trade-Offs for k-SUM. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.58

Author Details

Andrea Lincoln
Virginia Vassilevska Williams
Joshua R. Wang
R. Ryan Williams

References

  1. Amir Abboud, Kevin Lewi, and Ryan Williams. Losing weight by gaining edges. In Algorithms - ESA 2014 - 22th Annual European Symposium, Wroclaw, Poland, September 8-10, 2014. Proceedings, pages 1-12, 2014. Google Scholar
  2. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pages 39-51, 2014. Google Scholar
  3. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 18-21, 2014, pages 434-443, 2014. Google Scholar
  4. Nir Ailon and Bernard Chazelle. Lower bounds for linear degeneracy testing. J. ACM, 52(2):157-171, 2005. Google Scholar
  5. Amihood Amir, Timothy M. Chan, Moshe Lewenstein, and Noa Lewenstein. On hardness of jumbled indexing. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, 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 Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, pages 45-56, 2013. Google Scholar
  7. Ilya Baran, Erik D Demaine, and Mihai Patraşcu. Subquadratic algorithms for 3sum. In Algorithms and Data Structures, pages 409-421. Springer, 2005. Google Scholar
  8. Paul Beame, Raphaël Clifford, and Widad Machmouchi. Element distinctness, frequency moments, and sliding windows. In FOCS, pages 290-299, 2013. Google Scholar
  9. Paul Beame, Michael E. Saks, Xiaodong Sun, and Erik Vee. Time-space trade-off lower bounds for randomized computation of decision problems. J. ACM, 50(2):154-195, 2003. Google Scholar
  10. Manuel Blum, Robert W Floyd, Vaughan Pratt, Ronald L Rivest, and Robert E Tarjan. Time bounds for selection. Journal of computer and system sciences, 7(4):448-461, 1973. Google Scholar
  11. A. Czumaj and A. Lingas. Finding a heaviest triangle is not harder than matrix multiplication. In Proc. SODA, pages 986-994, 2007. Google Scholar
  12. Scott Diehl, Dieter van Melkebeek, and Ryan Williams. An improved time-space lower bound for tautologies. J. Comb. Optim., 22(3):325-338, 2011. Google Scholar
  13. Jeff Erickson. Lower bounds for linear satisfiability problems. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 22-24 January 1995. San Francisco, California., pages 388-395, 1995. Google Scholar
  14. Lance Fortnow, Richard J. Lipton, Dieter van Melkebeek, and Anastasios Viglas. Time-space lower bounds for satisfiability. J. ACM, 52(6):835-865, 2005. Google Scholar
  15. Anka Gajentaan and Mark H Overmars. On a class of O(n²) problems in computational geometry. Computational geometry, 5(3):165-185, 1995. Google Scholar
  16. Omer Gold and Micha Sharir. Improved bounds for 3sum, k-sum, and linear degeneracy. arXiv preprint arXiv:1512.05279, 2015. Google Scholar
  17. Allan Gronlund and Seth Pettie. Threesomes, degenerates, and love triangles. In Foundations of Computer Science (FOCS), 2014 IEEE 55th Annual Symposium on, pages 621-630. IEEE, 2014. Google Scholar
  18. R. Impagliazzo and R. Paturi. On the complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. Google Scholar
  19. Richard M Karp. Reducibility among combinatorial problems. Springer, 1972. Google Scholar
  20. Mihai Patrascu. Towards polynomial lower bounds for dynamic problems. In Proceedings of the forty-second ACM symposium on Theory of computing, pages 603-610. ACM, 2010. Google Scholar
  21. Seth Pettie and Vijaya Ramachandran. A shortest path algorithm for real-weighted undirected graphs. SIAM J. Comput., 34(6):1398-1431, 2005. Google Scholar
  22. Mihai Pătraşcu and Ryan Williams. On the possibility of faster sat algorithms. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA'10, pages 1065-1075, Philadelphia, PA, USA, 2010. Society for Industrial and Applied Mathematics. Google Scholar
  23. Richard Schroeppel and Adi Shamir. A T = O(2^n/2), S = O(2^n/4) algorithm for certain np-complete problems. SIAM journal on Computing, 10(3):456-464, 1981. Google Scholar
  24. Virginia Vassilevska and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 455-464. ACM, 2009. Google Scholar
  25. Joshua R Wang. Space-efficient randomized algorithms for k-sum. In Algorithms-ESA 2014, pages 810-829. Springer, 2014. Google Scholar
  26. R. Ryan Williams. Time-space tradeoffs for counting NP solutions modulo integers. Computational Complexity, 17(2):179-219, 2008. 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