Ziyang Liu, Sivaramakrishnan Natarajan, et al.
VLDB
We provide an O(n2log 1/δ) time randomized algorithm to check whether a given operation ο × S → S is associative (where n = |S| and δ > 0 is the error probability required of the algorithm). We prove that (for any constant δ) this performance is optimal up to a constant factor, even if the operation is 'cancellative'. No sub-n3 time algorithm was previously known for this task. More generally we give an O(nc) time randomized algorithm to check whether a collection of c-ary operations satisfy any given 'read-once' identity.
Ziyang Liu, Sivaramakrishnan Natarajan, et al.
VLDB
Leo Liberti, James Ostrowski
Journal of Global Optimization
B.K. Boguraev, Mary S. Neff
HICSS 2000
William Hinsberg, Joy Cheng, et al.
SPIE Advanced Lithography 2010