Removing Additive Structure in 3SUM-Based Reductions

Our work explores the hardness of 3SUM instances without certain additive structures, and its applications. As our main technical result, we show that solving 3SUM on a size-n integer set that avoids solutions to a + b = c + d for a, b = c, d still requires n 2-o(1) time, under the 3SUM hypothesis. Such sets are called Sidon sets and are well-studied in the field of additive combinatorics.

• Combined with previous reductions, this implies that the All-Edges Sparse Triangle problem on nvertex graphs with maximum degree √ n and at most n k/2 k-cycles for every k ≥ 3 requires n 2-o(1) time, under the 3SUM hypothesis. This can be used to strengthen the previous conditional lower bounds by Abboud, Bringmann, Khoury, and Zamir [STOC'22] of 4-Cycle Enumeration, Offline Approximate Distance Oracle and Approximate Dynamic Shortest Path. In particular, we show that no algorithm for the 4-Cycle Enumeration problem on n-vertex m-edge graphs with n o(1) delays has O(n 2-ε ) or O(m 4/3-ε ) pre-processing time for ε > 0. We also present a matching upper bound via simple modifications of the known algorithms for 4-Cycle Detection.

• A slight generalization of the main result also extends the result of Dudek, Gawrychowski, and Starikovskaya [STOC'20] on the 3SUM hardness of nontrivial 3-Variate Linear Degeneracy Testing (3-LDTs): we show 3SUM hardness for all nontrivial 4-LDTs.

The proof of our main technical result combines a wide range of tools: Balog-Szemerédi-Gowers theorem, sparse convolution algorithm, and a new almost-linear hash function with almost 3-universal guarantee for integers that do not have small-coefficient linear relations.