2 papers
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…