{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreickwvdtnqpqlvcswwb37ztyucbp5eozw3dot3gnge5qyvzldr3ojm",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mflbewgxgvl2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.20023v1",
  "publishedAt": "2026-02-24T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "László Kozma",
    "Michal Opler"
  ],
  "textContent": "**Authors:** László Kozma, Michal Opler\n\nMatrix multiplication is a fundamental task in almost all computational fields, including machine learning and optimization, computer graphics, signal processing, and graph algorithms (static and dynamic). Twin-width is a natural complexity measure of matrices (and more general structures) that has recently emerged as a unifying concept with important algorithmic applications. While the twin-width of a matrix is invariant to re-ordering rows and columns, most of its algorithmic applications to date assume that the input is given in a certain canonical ordering that yields a bounded twin-width contraction sequence. In general, efficiently finding such a sequence -- even for an approximate twin-width value -- remains a central and elusive open question. In this paper we show that a binary $n \\times n$ matrix of twin-width $d$ can be preprocessed in $\\widetilde{\\mathcal{O}}_d(n^2)$ time, so that its product with any vector can be computed in $\\widetilde{\\mathcal{O}}_d(n)$ time. Notably, the twin-width of the input matrix need not be known and no particular ordering of its rows and columns is assumed. If a canonical ordering is available, i.e., if the input matrix is $d$-twin-ordered, then the runtime of preprocessing and matrix-vector products can be further reduced to $\\mathcal{O}(n^2+dn)$ and $\\mathcal{O}(dn)$. Consequently, we can multiply two $n \\times n$ matrices in $\\widetilde{\\mathcal{O}}(n^2)$ time, when at least one of the matrices consists of 0/1 entries and has bounded twin-width. The results also extend to the case of bounded twin-width matrices with adversarial corruption. Our algorithms are significantly faster and simpler than earlier methods that involved first-order model checking and required both input matrices to be $d$-twin-ordered.",
  "title": "Fast and simple multiplication of bounded twin-width matrices"
}