Seminar Details
Algorithmically Distinguishing Irreducible Characters of the Symmetric Group
- Start Date: December 10, 2020
- Event Start Time: 5:00 PM
- Event End Time: 6:00 PM
- Seminar Series: Experimental Math Seminar
- Presenter(s): Timothy Chow - Princeton University
- Event Location: Online Event
- Event Additional Info: <p>Presented Via Zoom: <a href="https://rutgers.zoom.us/j/94346444480">https://rutgers.zoom.us/j/94346444480</a></p> <p> </p> <p>Password: 6564120420</p> <p> </p>
- Presentation Type: Stand Alone Presentation
- Abstract:
Abstract: Suppose χλ and χμ are two distinct irreducible characters of the symmetric group Sn. How hard is it to find a permutation π such that χλ(π) differs from χμ(π)? Surprisingly, this natural question seems not to have been considered before in the literature. One might expect that the problem is hard, since even determining whether χλ(π) is zero or not is in general NP-hard. A closely related problem is, given oracle access to a function that is promised to be an irreducible character of Sn, how many queries do we need to determine which irreducible character it is? We give an algorithm that solves this problem with polynomially many queries, and that also gives a polynomial time algorithm for the original problem. Coming up with our algorithm involved considerable experimentation. This is joint work with Jennifer Paulhus.
No previous knowledge of group characters will be assumed, all the necessary background will be reviewed.