Conference paper
Social networks and discovery in the enterprise (SaND)
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009
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.
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009
M.J. Slattery, Joan L. Mitchell
IBM J. Res. Dev
N.K. Ratha, A.K. Jain, et al.
Workshop CAMP 2000
Robert G. Farrell, Catalina M. Danis, et al.
RecSys 2012