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 n -vertex 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.

Authors

• Ce Jin 0001
• Yinzhan Xu

Keywords

• 3SUM
• additive combinatorics
• fine-grained complexity
• graph algorithms