The Computational Complexity of Rules for the Character Table of S_n
| dc.creator | Bernstein, Dan | |
| dc.date | 2003-09-14 | |
| dc.date.accessioned | 2026-07-07T05:01:06Z | |
| dc.date.available | 2026-07-07T05:01:06Z | |
| dc.description | The Murnaghan-Nakayama rule is the classical formula for computing the character table of S_n. Y. Roichman has recently discovered a rule for the Kazhdan-Lusztig characters of q-Hecke algebras of type A, which can also be used for the character table of S_n. For each of the two rules, we give an algorithm for computing entries in the character table of S_n. We then analyze the computational complexity of the two algorithms, and in the case of characters indexed by partitions in the (k,l)-hook, compare their complexities to each other. It turns out that the algorithm based on the Murnaghan-Nakayama rule requires far less operations than the other algorithm. We note the algorithms' complexities' relation to two enumeration problems of Young diagrams and Young tableaux. | |
| dc.description | 24 pages | |
| dc.identifier | https://arxiv.org/abs/math/0309225 | |
| dc.identifier | http://arxiv.org/abs/math/0309225 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/68557 | |
| dc.subject | Combinatorics | |
| dc.subject | Representation Theory | |
| dc.subject | 05A16 (Primary) 05E10 (Secondary) | |
| dc.title | The Computational Complexity of Rules for the Character Table of S_n | |
| dc.type | text |