Is a given binary operation * on a finite set X associative? We will see a O(n^2) time randomized algorithm for solving this problem (here n = |X|). If time permits, we will also see how the above algorithm can be extended for checking general "read-once" identities.
References:
- Jiri Matousek, Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra, American Mathematical Society, 2010
- Rajagopalan, Sridhar; Schulman, Leonard J. (2000). "Verification of Identities". SIAM Journal on Computing. 29 (4): 1155–1163
