Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Deterministic Monotone Min-Plus Product and Convolution
Ce Jin, Jaewoo Park, Barna Saha +1
The Monotone Min-Plus Product problem is a useful primitive that has seen many algorithmic applications over the past decade. In this problem, we are given two integer…
cs.DS2026
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…
cs.DS2024
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…