- To appear in Proc. 64th IEEE Symposium on Foundations of Computer Science (FOCS), 2023

In this paper we carefully combine Fredman's trick [SICOMP'76] and Matousek's approach for dominance product [IPL'91] to obtain powerful results in fine-grained complexity:

- Under the hypothesis that APSP for undirected graphs with edge weights in {1,2,...,n} requires n^{3-o(1)} time (when omega=2), we show a variety of conditional lower bounds, including an n^{7/3-o(1)} lower bound for unweighted directed APSP, and an n^{2.2-o(1)} lower bound for computing the Minimum Witness Product between two n x n Boolean matrices, even if omega=2, improving upon the trivial n^2 lower bound. Our techniques can also be used to reduce the unweighted directed APSP problem to other problems. In particular, we show that (when omega=2), if unweighted directed APSP requires n^{2.5-o(1)} time, then Minimum Witness Product requires n^{7/3-o(1)} time.
- We show that, surprisingly, many central problems in fine-grained complexity are equivalent to their natural counting versions. In particular, we show that Min-Plus Product and Exact Triangle are subcubically equivalent to their counting versions, and 3SUM is subquadratically equivalent to its counting version.
The approach also leads to subquadratic
*nondeterministic*algorithms for 3SUM counting. - We obtain new algorithms using new variants of the Balog-Szemeredi-Gowers theorem from additive combinatorics. For example, we get an O(n^{3.83}) time deterministic algorithm for exactly counting the number of shortest paths in an arbitrary weighted graph, improving the textbook O~(n^4) time algorithm. We also get faster algorithms for 3SUM in preprocessed universes, and deterministic algorithms for 3SUM on monotone sets in {1,2,...,n}^d.

The 3SUM hypothesis, the APSP hypothesis and SETH are the three main hypotheses in fine-grained complexity. So far, within the area, the first two hypotheses have mainly been about integer inputs in the Word RAM model of computation. The "Real APSP" and "Real 3SUM" hypotheses, which assert that the APSP and 3SUM hypotheses hold for real-valued inputs in a reasonable version of the Real RAM model, are even more believable than their integer counterparts.

Under the very believable hypothesis that at least one of the Integer 3SUM hypothesis, Integer APSP hypothesis or SETH is true, Abboud, Vassilevska W. and Yu [STOC 2015] showed that a problem called Triangle Collection requires n^{3-o(1)} time on an n-node graph.

Our main result is a nontrivial lower bound for a slight generalization of Triangle Collection, called All-Color-Pairs Triangle Collection, under the even more believable hypothesis that at least one of the Real 3SUM, the Real APSP, and the OV hypotheses is true. Combined with slight modifications of prior reductions, we obtain polynomial conditional lower bounds for problems such as the (static) ST-Max Flow problem and dynamic Max Flow, now under the new weaker hypothesis.

Our main result is built on the following two lines of reductions.

- Real APSP and Real 3SUM hardness for the All-Edges Sparse Triangle problem. Prior reductions only worked from the integer variants of these problems.
- Real APSP and OV hardness for a variant of the Boolean Matrix Multiplication problem.

Given a set S of n numbers, the 3SUM problem asks to determine whether there exist three elements a,b,c in S such that a+b+c = 0. The related Convolution-3SUM problem asks to determine whether there exist a pair of indices i,j such that A[i]+A[j] = A[i+j], where A is a given array of nnumbers.

When the numbers are integers, a *randomized* reduction from 3SUM to Convolution-3SUM was given in a seminal paper by Patrascu [STOC 2010], which was later improved by Kopelowitz, Pettie, and Porat [SODA 2016] with an O(log n) factor slowdown. In this paper, we present a simple *deterministic* reduction from 3SUM to Convolution-3SUM for integers bounded by U. We also describe additional ideas to obtaining further improved reductions, with only a (loglog n)^{O(1)} factor slowdown in the randomized case, and a (log U)^{O(1)} factor slowdown in the deterministic case.

- In Proc. 3rd SIAM Symposium on Simplicity in Algorithms (SOSA), pages 1-7, 2020 (SOSA best paper)

We present an algorithm that solves the 3SUM problem for n real numbers in O((n^2/log^2n) (loglog n)^{O(1)}) time, improving previous solutions by about a logarithmic factor. Our framework for shaving off two logarithmic factors can be applied to other problems, such as (median,+)-convolution/matrix multiplication and algebraic generalizations of 3SUM. We also obtain the first subquadratic results on some 3SUM-hard problems in computational geometry, for example, deciding whether (the interiors of) a constant number of simple polygons have a common intersection.

- PDF file
- ACM Transactions on Algorithms, 16(1): 7:1-7:23, 2020 (SODA special issue)
- In Proc. 29th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 881-897, 2018

We present a collection of new results on problems related to 3SUM, including:

- The first truly subquadratic algorithm for
- computing the (min,+) convolution for monotone increasing sequences with integer values bounded by O(n),
- solving 3SUM for monotone sets in 2D with integer coordinates bounded by O(n), and
- preprocessing a binary string for histogram indexing (also called jumbled indexing).

- The first algorithm for histogram indexing for any constant alphabet size that achieves truly subquadratic preprocessing time and truly sublinear query time.
- A truly subquadratic algorithm for integer 3SUM in the case when the given set can be partitioned into n^{1-delta} clusters each covered by an interval of length n, for any constant delta > 0.
- An algorithm to preprocess any set of n integers so that subsequently 3SUM on any given subset can be solved in O(n^{13/7} polylog n) time.

- Preliminary arXiv version
- PDF talk slides
- In Proc. 47th ACM Symposium on Theory of Computing (STOC), pages 31-40, 2015

Jumbled indexing is the problem of indexing a text T for queries that ask whether there is a substring of T matching a pattern represented as a Parikh vector, i.e., the vector of frequency counts for each character. Jumbled indexing has garnered a lot of interest in the last four years. There is a naive algorithm that preprocesses all answers in O(n^2 |Sigma|) time allowing quick queries afterwards, and there is another naive algorithm that requires no preprocessing but has O(n log |Sigma|) query time. Despite a tremendous amount of effort there has been little improvement over these running times.

In this paper we provide good reason for this. We show that, under a 3SUM-hardness assumption, jumbled indexing for alphabets of size omega(1) requires Omega(n^{2-epsilon}) preprocessing time or Omega(n^{1-delta}) query time for any epsilon,delta>0. In fact, under a stronger 3SUM-hardness assumption, for any constant alphabet size r >= 3 there exist describable fixed constant epsilon_r and delta_r such that jumbled indexing requires Omega(n^{2-epsilon_r}) preprocessing time or Omega(n^{1-delta_r}) query time.

- PDF file | arXiv version
- In Proc. 41st International Colloquium on Automata, Languages, and Programming (ICALP), Lecture Notes in Computer Science, volume 8572, pages 114-125, 2014

The documents contained in this directory are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Timothy Chan (Last updated Aug 2023)