7 papers
Beyond 3SUM-Hardness for Geometric Problems
Nick Fischer
Since the early days of fine-grained complexity, many geometric problems have been shown to require quadratic time under the 3SUM Hypothesis. But as the 3SUM Hypothesis was recentl…
Preprocessed 3SUM: From Reals to Integers
Nick Fischer, Jonas Schmidt
The Preprocessed 3SUM problem asks to preprocess a set of numbers so that we can quickly decide whether a query subset contains a solution . The bes…
Min-Plus Convolution Lower Bounds via a Higher-Order BSG Theorem
Nick Fischer, Ce Jin, Yinzhan Xu
Min-Plus Convolution is a central problem in fine-grained complexity, and the associated Min-Plus Convolution Hypothesis forms the basis for a wide range of conditional lower bound…
3SUM Is Really Hard: A Real-to-Integer Reduction
Nick Fischer, Adam Polak, Jonas Schmidt
We show that if the 3SUM problem on integer-valued inputs can be solved in truly subquadratic time, then it can also be solved in truly subquadratic time on real-valued inputs. Thi…
Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection
Bartłomiej Dudek, Nick Fischer, Geri Gokaj +4
We revisit the complexity of verifying basic identities, such as associativity and distributivity, on a given finite algebraic structure. In particular, while Rajagopalan and Schul…
New Applications of 3SUM-Counting in Fine-Grained Complexity and Pattern Matching
Nick Fischer, Ce Jin, Yinzhan Xu
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…
Deterministic 3SUM-Hardness
Nick Fischer, Piotr Kaliciak, Adam Polak
As one of the three main pillars of fine-grained complexity theory, the 3SUM problem explains the hardness of many diverse polynomial-time problems via fine-grained reductions. Man…