Mittagsseminar (by J. Lengler, K. Bringmann, B. Gärtner, M. Hoffmann, R. Kyng, D.Steurer, V. Traub)

Date and Time: Thursday, March 19, 2026, 12:15 pm

Duration: 30 minutes

Location: OAT S15

Speaker: Mirza Redzic (Karlsruhe Institute of Technology)

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

We revisit 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 ⊙: S×S→S in optimal time O(|S|²), they left the open problem of finding any subcubic algorithm for verifying distributivity of given operations ⊙,⊕: S×S→S.

Our results are as follows:
1. We resolve the open problem by Rajagopalan and Schulman by devising an algorithm verifying distributivity in strongly subcubic time O(|S|^ω), together with a matching conditional lower bound based on the Triangle Detection Hypothesis.
2. We propose arithmetic progression detection in small universes as a consequential algorithmic challenge: We show that unless we can detect 4-term arithmetic progressions in a set X⊂eq;{1,…,N} in time O(N^2-ε), then (a) the 3-uniform 4-hyperclique hypothesis is true, and (b) verifying certain identities requires running time |S|^3-o(1).
3. 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: (1) verifiable in randomized time O(|S|²), (2) verifiable in randomized time O(|S|^ω) with a matching lower bound from triangle detection, or (3) trivially verifiable in time O(|S|³) with a matching lower bound from hardness of 4-term arithmetic progression detection.
4. 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.

Upcoming talks     |     All previous talks     |     Talks by speaker     |     Upcoming talks in iCal format (beta version!)

Previous talks by year:   2026  2025  2024  2023  2022  2021  2020  2019  2018  2017  2016  2015  2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  1997  1996  

Information for students and suggested topics for student talks

Automatic MiSe System Software Version 1.4803M   |   admin login