New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching

The 3SUM problem is one of the cornerstones of fine-grained complexity. Its study has led to countless lower bounds, but as has been sporadically observed before-and as we will demonstrate again-insights on 3SUM can also lead to algorithmic applications.

The starting point of our work is that we spend a lot of technical effort to develop new algorithms for 3SUM-type problems such as approximate 3SUM-counting, small-doubling 3SUMcounting, and a deterministic subquadratic-time algorithm for the celebrated Balog-Szemerédi-Gowers theorem from additive combinatorics. All of these are relevant in their own right and may prove useful for future research on 3SUM.

But perhaps even more excitingly, as consequences of these tools, we derive diverse new results in fine-grained complexity and pattern matching algorithms, answering open questions from many unrelated research areas. Specifically: • A recent line of research on the "short cycle removal" technique culminated in tight 3SUMbased lower bounds for various graph problems via randomized fine-grained reductions [Abboud, Bringmann, Fischer; STOC '23] [Jin, Xu; STOC '23]. In this paper we derandomize the reduction to the important 4-Cycle Listing problem, answering a main open question of [Fischer, Kaliciak, Polak; ITCS '24]. • We establish that #3SUM and 3SUM are fine-grained equivalent under deterministic reductions, derandomizing a main result of [Chan, Vassilevska Williams, Xu; STOC '23].

• We give a deterministic algorithm for the (1 + ǫ)-approximate Text-to-Pattern Hamming Distances problem in time n 1+o(1) • ǫ -1 . While there is a large body of work addressing the randomized complexity, this is the first deterministic improvement over Karloff's O(nǫ -2 )time algorithm in over 30 years.

• In the k-Mismatch Constellation problem the input consists of two integer sets A, B ⊆ [N ], and the goal is to test whether there is a shift c such that |(c + B) A| ≤ k (i.e., whether B shifted by c matches A up to k mismatches). For moderately small k the previously best running time was O(|A| • k) [Cardoze, Schulman; FOCS '98] [Fischer; SODA '24]. We give a faster |A| • k 2/3 • N o(1) -time algorithm in the regime where |B| = Θ(|A|). This result also has implications for the k-Mismatch String Matching with Wildcards problem.