Tata Institute of Fundamental Research
Is it associative?
STCS Student Seminar
Speaker:
Shanthanu Suresh Rai (TIFR)
Organiser:
Varun Ramanathan
Date:
Friday, 6 Oct 2023, 15:45 to 17:15
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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
| Speaker: | Shanthanu Suresh Rai (TIFR) |
| Organiser: | Varun Ramanathan |
| Date: | Friday, 6 Oct 2023, 15:45 to 17:15 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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