Vassilevska Williams, Virginia
3SUM and Related Problems in FineGrained Complexity (Invited Talk)
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 FineGrained Complexity (FGC) states that 3SUM requires n^{2o(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 3SUMConvolution (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 3SUMConvolution, many 3SUMbased 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 runtimeequivalent 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 AllNumbers3SUM: 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, 3SUMConvolution and AllNumbers 3SUM are (n²,n²)finegrained 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)finegrained 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)finegrained 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 AllPairs 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^{3o(1)} time is needed to solve APSP in graphs with integer edge weights in the wordRAM model with O(log n) bit words. It is unknown whether APSP and 3SUM are finegrained reducible to each other, in either direction. The two problems are very similar. Problems such as (min,+)convolution (believed to require n^{2o(1)} time) have tight finegrained reductions to both APSP and 3SUM, and both 3SUM and APSP have tight finegrained 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.
BibTeX  Entry
@InProceedings{vassilevskawilliams:LIPIcs.SoCG.2021.2,
author = {Vassilevska Williams, Virginia},
title = {{3SUM and Related Problems in FineGrained Complexity}},
booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)},
pages = {2:12:2},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771849},
ISSN = {18688969},
year = {2021},
volume = {189},
editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13801},
URN = {urn:nbn:de:0030drops138014},
doi = {10.4230/LIPIcs.SoCG.2021.2},
annote = {Keywords: finegrained complexity}
}
02.06.2021
Keywords: 

finegrained complexity 
Seminar: 

37th International Symposium on Computational Geometry (SoCG 2021)

Issue date: 

2021 
Date of publication: 

02.06.2021 