{
  "id": "2009.11391",
  "version": "v1",
  "published": "2020-09-23T21:40:15.000Z",
  "updated": "2020-09-23T21:40:15.000Z",
  "title": "Bad and good news for Strassen's laser method: Border rank of the 3x3 permanent and strict submultiplicativity",
  "authors": [
    "Austin Conner",
    "Hang Huang",
    "J. M. Landsberg"
  ],
  "categories": [
    "math.AG",
    "cs.CC"
  ],
  "abstract": "We determine the border ranks of tensors that could potentially advance the known upper bound for the exponent $\\omega$ of matrix multiplication. The Kronecker square of the small $q=2$ Coppersmith-Winograd tensor equals the $3\\times 3$ permanent, and could potentially be used to show $\\omega=2$. We prove the negative result for complexity theory that its border rank is $16$, resolving a longstanding problem. Regarding its $q=4$ skew cousin in $ C^5\\otimes C^5\\otimes C^5$, which could potentially be used to prove $\\omega\\leq 2.11$, we show the border rank of its Kronecker square is at most $42$, a remarkable sub-multiplicativity result, as the square of its border rank is $64$. We also determine moduli spaces $\\underline{VSP}$ for the small Coppersmith-Winograd tensors.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2020-09-23T21:40:15.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68Q15",
      "15A69",
      "14L35"
    ],
    "keywords": [
      "border rank",
      "strassens laser method",
      "3x3 permanent",
      "strict submultiplicativity",
      "kronecker square"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}