SUMMARY
Suppose that ??\chi_\lambda and ?µ\chi_\mu are distinct irreducible characters of the symmetric group SnS_n. We give an algorithm that, in time polynomial in nn, constructs p?Sn\pi\in S_n such that ??(p)\chi_\lambda(\pi) is provably different from ?µ(p)\chi_\mu(\pi). In fact, we show a little more. Suppose f=??f = \chi_\lambda for some irreducible character ??\chi_\lambda of SnS_n, but we do not know ?\lambda, and we are given only oracle access to ff. We give an algorithm that determines ?\lambda, using a number of queries to ff that is polynomial in nn. Each query can be computed in time polynomial in nn by someone who knows ?\lambda.