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.DS2025
Equivalences between Non-trivial Variants of 3LDT and Conv3LDT
BartÅomiej Dudek, PaweÅ Gawrychowski, Tatiana Starikovskaya
The popular 3SUM conjecture states that there is no strongly subquadratic time algorithm for checking if a given set of integers contains three distinct elements su…