2024/10/28 by Fischer, Nick, Jin, Ce, Xu, Yinzhan · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2410.20764
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 3SUM-counting, and a deterministic subquadratic-time algorithm for the celebrated Balog-Szemerédi-Gowers theorem from additive combinatorics. 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 3SUM-based 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. - We establish that #3SUM and 3SUM are fine-grained equivalent under deterministic reductions. - We give a deterministic algorithm for the (1+ε)-approximate Text-to-Pattern Hamming Distances problem in time n1+o(1) ⋅ ε-1. - 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| ⋅ k2/3 ⋅ No(1)-time algorithm in the regime where |B| = Θ(|A|).