Department of

Mathematics


Seminar Calendar
for events the day of Thursday, August 6, 2020.

     .
events for the
events containing  

(Requires a password.)
More information on this calendar program is available.
Questions regarding events or the calendar should be directed to Tori Corkery.
      July 2020             August 2020           September 2020   
 Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
           1  2  3  4                      1          1  2  3  4  5
  5  6  7  8  9 10 11    2  3  4  5  6  7  8    6  7  8  9 10 11 12
 12 13 14 15 16 17 18    9 10 11 12 13 14 15   13 14 15 16 17 18 19
 19 20 21 22 23 24 25   16 17 18 19 20 21 22   20 21 22 23 24 25 26
 26 27 28 29 30 31      23 24 25 26 27 28 29   27 28 29 30         
                        30 31                                      

Thursday, August 6, 2020

10:00 am in Zoom,Thursday, August 6, 2020

Algorithmically Distinguishing Irreducible Characters of the Symmetric Group

Timothy Chow   [email] (IDA, Princeton)

Abstract: Suppose $\chi_\lambda$ and $\chi_\mu$ are two distinct irreducible characters of the symmetric group $S_n$. How hard is it to find a permutation $\pi$ such that $\chi_\lambda(\pi)$ differs from $\chi_\mu(\pi)$? 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 $\chi_\lambda(\pi)$ is zero or not is in general $\sf NP$-$\sf hard$. A slightly harder problem is, given oracle access to a function that is promised to be an irreducible character of $S_n$, 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. The method is purely combinatorial and relies on the Murnaghan-Nakayama rule. This is joint work with Jennifer Paulhus. Please email Colleen at cer2 (at) illinois (dot) edu for the Zoom ID and password.