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 $k$-SUM hypothesis has emerged as a satisfying explanation of long-standing time barriers for a variety of algorithmic problems. Yet to this day, the…