Removing Additive Structure in 3SUM-Based Reductions
share
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.
READ FULL TEXT