4 papers
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…
Approximating Pareto Sum via Bounded Monotone Min-Plus Convolution
Geri Gokaj, Marvin Künnemann, Sabine Storandt +1
The Pareto sum of two-dimensional point sets and in is defined as the skyline of the points in their Minkowski sum. The problem of efficiently computing the…
Computing Hausdorff Distances Under Translations: The Interplay of Dimensionality, Symmetry and Discreteness
Sebastian Angrick, Kevin Buchin, Geri Gokaj +1
To measure the shape similarity of point sets, various notions of the Hausdorff distance under translation are widely studied. In this context, for an -point set and -poi…
Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Integer Linear Arithmetic
Geri Gokaj, Marvin Künnemann
In the last three decades, the -SUM hypothesis has emerged as a satisfying explanation of long-standing time barriers for a variety of algorithmic problems. Yet to this day, the…