3SUM and Related Problems in Fine-Grained Complexity (Invited Talk)

Author Virginia Vassilevska Williams



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.2.pdf
  • Filesize: 379 kB
  • 2 pages

Document Identifiers

Author Details

Virginia Vassilevska Williams
  • Massachusetts Institute of Technology, Cambridge, MA, USA

Cite AsGet BibTex

Virginia Vassilevska Williams. 3SUM and Related Problems in Fine-Grained Complexity (Invited Talk). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.2

Abstract

3SUM is a simple to state problem: given a set S of n numbers, determine whether S contains three a,b,c so that a+b+c = 0. The fastest algorithms for the problem run in n² poly(log log n)/(log n)² time both when the input numbers are integers [Ilya Baran et al., 2005] (in the word RAM model with O(log n) bit words) and when they are real numbers [Timothy M. Chan, 2020] (in the real RAM model). A hypothesis that is now central in Fine-Grained Complexity (FGC) states that 3SUM requires n^{2-o(1)} time (on the real RAM for real inputs and on the word RAM with O(log n) bit numbers for integer inputs). This hypothesis was first used in Computational Geometry by Gajentaan and Overmars [A. Gajentaan and M. Overmars, 1995] who built a web of reductions showing that many geometric problems are hard, assuming that 3SUM is hard. The web of reductions within computational geometry has grown considerably since then (see some citations in [V. Vassilevska Williams, 2018]). A seminal paper by Pǎtraşcu [Mihai Pǎtraşcu, 2010] showed that the integer version of the 3SUM hypothesis can be used to prove polynomial conditional lower bounds for several problems in data structures and graph algorithms as well, extending the implications of the hypothesis to outside computational geometry. Pǎtraşcu proved an important tight equivalence between (integer) 3SUM and a problem called 3SUM-Convolution (see also [Timothy M. Chan and Qizheng He, 2020]) that is easier to use in reductions: given an integer array a of length n, do there exist i,j ∈ [n] so that a[i]+a[j] = a[i+j]. From 3SUM-Convolution, many 3SUM-based hardness results have been proven: e.g. to listing graphs in triangles, dynamically maintaining shortest paths or bipartite matching, subset intersection and many more. It is interesting to consider more runtime-equivalent formulations of 3SUM, with the goal of uncovering more relationships to different problems. The talk will outline some such equivalences. For instance, 3SUM (over the reals or the integers) is equivalent to All-Numbers-3SUM: given a set S of n numbers, determine for every a ∈ S whether there are b,c ∈ S with a+b+c = 0 (e.g. [V. Vassilevska Williams and R. Williams, 2018]). The equivalences between 3SUM, 3SUM-Convolution and All-Numbers 3SUM are (n²,n²)-fine-grained equivalences that imply that if there is an O(n^{2-ε}) time algorithm for one of the problems for ε > 0, then there is also an O(n^{2-ε'}) time algorithm for the other problems for some ε' > 0. More generally, for functions a(n),b(n), there is an (a,b)-fine-grained reduction [V. Vassilevska Williams, 2018; V. Vassilevska Williams and R. Williams, 2010; V. Vassilevska Williams and R. Williams, 2018] from problem A to problem B if for every ε > 0 there is a δ > 0 and an O(a(n)^{1-δ}) time algorithm for A that does oracle calls to instances of B of sizes n₁,…,n_k (for some k) so that ∑_{j = 1}^k b(n_j)^{1-ε} ≤ a(n)^{1-δ}. With such a reduction, an O(b(n)^{1-ε}) time algorithm for B can be converted into an O(a(n)^{1-δ}) time algorithm for A by replacing the oracle calls by calls to the B algorithm. A and B are (a,b)-fine-grained equivalent if A (a,b)-reduces to B and B (b,a)-reduces to A. One of the main open problems in FGC is to determine the relationship between 3SUM and the other central FGC problems, in particular All-Pairs Shortest Paths (APSP). A classical graph problem, APSP in n node graphs has been known to be solvable in O(n³) time since the 1950s. Its fastest known algorithm runs in n³/exp(√{log n}) time [Ryan Williams, 2014]. The APSP Hypothesis states that n^{3-o(1)} time is needed to solve APSP in graphs with integer edge weights in the word-RAM model with O(log n) bit words. It is unknown whether APSP and 3SUM are fine-grained reducible to each other, in either direction. The two problems are very similar. Problems such as (min,+)-convolution (believed to require n^{2-o(1)} time) have tight fine-grained reductions to both APSP and 3SUM, and both 3SUM and APSP have tight fine-grained reductions to problems such as Exact Triangle [V. Vassilevska Williams and R. Williams, 2018; V. Vassilevska and R. Williams, 2009; V. Vassilevska Williams and Ryan Williams, 2013] and (since very recently) Listing triangles in sparse graphs [Mihai Pǎtraşcu, 2010; Tsvi Kopelowitz et al., 2016; V. Vassilevska Williams and Yinzhan Xu, 2020]. The talk will discuss these relationships and some of their implications, e.g. to dynamic algorithms.

Subject Classification

ACM Subject Classification
  • Theory of computation
  • Theory of computation → Design and analysis of algorithms
Keywords
  • fine-grained complexity

Metrics

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

References

  1. Ilya Baran, Erik D. Demaine, and Mihai Pǎtraşcu. Subquadratic algorithms for 3sum. In Algorithms and Data Structures, 9th International Workshop, WADS 2005, Waterloo, Canada, August 15-17, 2005, Proceedings, pages 409-421, 2005. Google Scholar
  2. Timothy M. Chan. More logarithmic-factor speedups for 3sum, (median, +)-convolution, and some geometric 3sum-hard problems. ACM Trans. Algorithms, 16(1):7:1-7:23, 2020. Google Scholar
  3. Timothy M. Chan and Qizheng He. Reducing 3sum to convolution-3sum. In Martin Farach-Colton and Inge Li Gørtz, editors, 3rd Symposium on Simplicity in Algorithms, SOSA 2020, Salt Lake City, UT, USA, January 6-7, 2020, pages 1-7. SIAM, 2020. Google Scholar
  4. A. Gajentaan and M. Overmars. On a class of O(n²) problems in computational geometry. Computational Geometry, 5(3):165-185, 1995. Google Scholar
  5. Allan Grønlund and Seth Pettie. Threesomes, degenerates, and love triangles. J. ACM, 65(4):22:1-22:25, 2018. Google Scholar
  6. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3sum conjecture. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 1272-1287, 2016. Google Scholar
  7. Mihai Pǎtraşcu. Towards polynomial lower bounds for dynamic problems. In Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pages 603-610, 2010. Google Scholar
  8. V. Vassilevska and R. Williams. Finding, minimizing, and counting weighted subgraphs. In Proc. STOC, pages 455-464, 2009. Google Scholar
  9. V. Vassilevska Williams and R. Williams. Subcubic equivalences between path, matrix and triangle problems. In Proc. FOCS, pages 645-654, 2010. Google Scholar
  10. V. Vassilevska Williams and R. Williams. Subcubic equivalences between path, matrix and triangle problems. Journal of the ACM, 2018. to appear. Google Scholar
  11. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians (ICM 2018), pages 3447-3487, 2018. URL: https://doi.org/10.1142/9789813272880_0188.
  12. Virginia Vassilevska Williams and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. SIAM J. Comput., 42(3):831-854, 2013. Google Scholar
  13. Virginia Vassilevska Williams and Yinzhan Xu. Monochromatic triangles, triangle listing and APSP. In 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 786-797. IEEE, 2020. Google Scholar
  14. Ryan Williams. Faster all-pairs shortest paths via circuit complexity. In Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31-June 03, 2014, pages 664-673, 2014. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail