{
  "id": "math/0309225",
  "version": "v1",
  "published": "2003-09-14T09:57:40.000Z",
  "updated": "2003-09-14T09:57:40.000Z",
  "title": "The Computational Complexity of Rules for the Character Table of S_n",
  "authors": [
    "Dan Bernstein"
  ],
  "comment": "24 pages",
  "categories": [
    "math.CO",
    "math.RT"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2003-09-14T09:57:40.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A16",
      "05E10"
    ],
    "keywords": [
      "character table",
      "computational complexity",
      "murnaghan-nakayama rule",
      "q-hecke algebras",
      "young tableaux"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 24,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2003math......9225B"
    }
  }
}