DIMACS Discrete Mathematics/Theory of Computing Seminar
Title:
Verifying Associativity and other Identities
Speaker:
Sridhar Rajagopalan
DIMACS
Place:
Seminar Room 431, CoRE Building,
Busch Campus, Rutgers University.
Time:
4:30 PM
Tuesday, April 9, 1996
Abstract:
Given a "multiplication" table how efficiently can you verify that
the operation is associative? What about other identities (distributivity,
for instance)?
We provide optimal randomized algorithms for this and other similar questions.