8 papers · 1 filter
Real-to-Integer Reduction for All-Pairs Shortest Paths
Nick Fischer, Adam Polak, Jonas Schmidt
Efficient graph algorithms often use techniques that are specific to integer-valued inputs and do not work for real-valued versions of the problems. Is it a limitation of current t…
The Hyperclique Hypothesis is False
Nick Fischer
The Hyperclique Hypothesis postulates that, for all constants , detecting a -clique in an -uniform hypergraph with vertices requires time . This…
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…