Classifying Identities: Subcubic Distributivity Checking and Hardness from Arithmetic Progression Detection

Werevisit the complexity of verifying basic identities, such as associativity and distributivity, on a given finite algebraic structure. In particular, while Rajagopalan and Schulman (FOCS’96, SICOMP’00) gave a surprising randomized algorithm to verify associativity of an operation ⊙ : 𝑆 × 𝑆 → 𝑆 in optimal time 𝑂(|𝑆|2), they left open the problem of finding any subcubic algorithm for verifying distributivity of given operations ⊙, ⊕ : 𝑆 × 𝑆 → 𝑆. Weresolve the open problem by Rajagopalan and Schulman by devising an algorithm verifying distributivity in strongly subcubic
time 𝑂(|𝑆|𝜔), together with a matching conditional lower bound based on the Triangle Detection Hypothesis. We propose arithmetic progression detection in small universes as a consequential algorith mic challenge: We show that unless 4-term arithmetic progressions in a set 𝑋 ⊆ {1,...,𝑁} can be detected in time𝑂(𝑁2−𝜖), then the 3-uniform 4-hyperclique hypothesis is true, and verifying certain identities requires running time |𝑆|3−𝑜(1). A careful combination of our algorithmic and hardness ideas allows us to fully classify a natural subclass of identities: Specifically, any 3-variable identity over binary operations in which no side is a subexpression of the other is either verifiable in randomized time 𝑂(|𝑆|2), verifiable in randomized time 𝑂(|𝑆|𝜔) with a matching lower bound from trian gle detection, or trivially verifiable in time 𝑂(|𝑆|3) with a matching
... mehr
lower bound from hardness of 4-term arithmetic progression de tection. Finally, we obtain near-optimal algorithms for verifying whether a given algebraic structure forms a field or ring, and show that counting the number of distributive triples is conditionally
harder than verifying distributivity.