Showing cs.CCShow all
2 papers · 1 filter
cs.CC2025
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…
cs.CC2020
Finding Small Satisfying Assignments Faster Than Brute Force: A Fine-grained Perspective into Boolean Constraint Satisfaction
Marvin Künnemann, Dániel Marx
To study the question under which circumstances small solutions can be found faster than by exhaustive search (and by how much), we study the fine-grained complexity of Boolean con…