DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2026.11

Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?

Authors: Cornelius Brand, Radu Curticapean, Petteri Kaski, Baitian Li, Ian Orzel, Tim Seppelt, and Jiaheng Wang

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract

The complexity of bilinear maps (equivalently, of 3-mode tensors) has been studied extensively, most notably in the context of matrix multiplication. While circuit complexity and tensor rank coincide asymptotically for 3-mode tensors, this correspondence breaks down for d ≥ 4 modes. As a result, the complexity of d-mode tensors for larger fixed d remains poorly understood, despite its relevance, e.g., in fine-grained complexity. Our paper explores this intermediate regime. First, we give a "graph-theoretic" proof of Strassen’s 2ω/3 bound on the asymptotic rank exponent of 3-mode tensors. Our proof directly generalizes to an upper bound of (d-1)ω/3 for d-mode tensors. Using refined techniques available only for d ≥ 4 modes, we improve this bound beyond the current state of the art for ω. We also obtain a bound of d/2+1 on the asymptotic exponent of circuit complexity of generic d-mode tensors and optimized bounds for d ∈ {4,5}. To the best of our knowledge, asymptotic circuit complexity (rather than rank) of tensors has not been studied before. To obtain a robust theory, we first ask whether low complexity of T and U imply low complexity of their Kronecker product T ⊗ U. While this crucially holds for rank (and thus for circuit complexity in 3 modes), we show that assumptions from fine-grained complexity rule out such a submultiplicativity for the circuit complexity of tensors with many modes. In particular, assuming the Hyperclique Conjecture, this failure occurs already for d = 8 modes. Nevertheless, we can salvage a restricted notion of submultiplicativity. From a technical perspective, our proofs heavily make use of the graph tensors T_H, as employed by Christandl and Zuiddam (Comput. Complexity 28 (2019) 27-56) and Christandl, Vrana and Zuiddam (Comput. Complexity 28 (2019) 57-111), whose modes correspond to the vertices of undirected graphs H. We make the simple but conceptually crucial observation that Kronecker products T_G ⊗ T_H are isomorphic to T_{G+H}, and that G and H may also be fractional graphs. By asymptotically converting generic tensors to specific graph tensors, we can use nontrivial results from algorithmic graph theory to study the rank and complexity of d-mode tensors for fixed d.

Cite as

Cornelius Brand, Radu Curticapean, Petteri Kaski, Baitian Li, Ian Orzel, Tim Seppelt, and Jiaheng Wang. Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{brand_et_al:LIPIcs.CCC.2026.11,
  author =	{Brand, Cornelius and Curticapean, Radu and Kaski, Petteri and Li, Baitian and Orzel, Ian and Seppelt, Tim and Wang, Jiaheng},
  title =	{{Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.11},
  URN =		{urn:nbn:de:0030-drops-270530},
  doi =		{10.4230/LIPIcs.CCC.2026.11},
  annote =	{Keywords: arithmetic circuits, tensor rank, bilinear complexity, graph tensors}
}

Document

DOI: 10.4230/LIPIcs.CCC.2026.36

Asymptotic Rank Speedup Theorems, Revisited

Authors: Josh Alman and Baitian Li

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract

Motivated by fast matrix multiplication and recent connections between asymptotic tensor rank and fine-grained complexity, we revisit classical tools from the matrix multiplication literature and develop a framework for obtaining improved asymptotic rank upper bounds for tensors beyond matrix multiplication. In the 1980s, Coppersmith-Winograd and Strassen discovered a series of speedup theorems for asymptotic rank: in certain regimes, one can extract additional terms from a border rank upper bound on a tensor T, and then use these terms to obtain an improved asymptotic rank of T. We establish general speedup theorems that subsume these results and enable quantitative improvements. Two representative applications are: 1) The asymptotic rank of the small Coppersmith-Winograd tensor cw_q is less than its border rank. For instance, we prove ̰{R}(cw₂) < 3.931, improving on ̲{R}(cw₂) = 4. It is known that ̰{R}(cw₂) = 3 would imply ω = 2. 2) A general improvement over Strassen’s bound: we obtain an upper bound below d^{2ω/3} on the asymptotic rank of any d× d× d tensor. To make full use of speedups, we analyze degenerations in which both sides are nontrivial direct sums, a setting where the optimal quantitative bound one can achieve was previously unclear. We do so via an approach we call Strassen calculus: a systematic method for converting such degeneration data into explicit asymptotic rank bounds using Strassen’s theory of the asymptotic spectrum.

Cite as

Josh Alman and Baitian Li. Asymptotic Rank Speedup Theorems, Revisited. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 36:1-36:42, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{alman_et_al:LIPIcs.CCC.2026.36,
  author =	{Alman, Josh and Li, Baitian},
  title =	{{Asymptotic Rank Speedup Theorems, Revisited}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{36:1--36:42},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.36},
  URN =		{urn:nbn:de:0030-drops-270780},
  doi =		{10.4230/LIPIcs.CCC.2026.36},
  annote =	{Keywords: tensor rank, matrix multiplication, Coppersmith-Winograd tensor, asymptotic spectrum}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.138

Counting Perfect Matchings and Hamiltonian Cycles Faster

Authors: Baitian Li

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

We show that the hafnian of a symmetric 2n× 2n matrix of poly(n)-bit integers (which counts the number of perfect matchings of a 2n-vertex graph) and the number of Hamiltonian cycles of an n-vertex directed graph can be computed in time 2^{n-Ω(√n)}, improving and generalizing an earlier algorithm of Björklund, Kaski, and Williams (Algorithmica 2019) that runs in time 2^{n - Ω(√{n/log log n})}. A key tool of our approach is the design of a data structure that supports fast evaluation of high-order derivatives of hafnian and Hamiltonian cycles, which integrates with the new approach on multivariate multipoint evaluation by Bhargava, Ghosh, Guo, Kumar, and Umans (FOCS 2022, JACM 2024).

Cite as

Baitian Li. Counting Perfect Matchings and Hamiltonian Cycles Faster. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 138:1-138:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{li:LIPIcs.ICALP.2026.138,
  author =	{Li, Baitian},
  title =	{{Counting Perfect Matchings and Hamiltonian Cycles Faster}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{138:1--138:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.138},
  URN =		{urn:nbn:de:0030-drops-265278},
  doi =		{10.4230/LIPIcs.ICALP.2026.138},
  annote =	{Keywords: permanent, hafnian, Hamiltonian cycle, Kakeya sets}
}

Search Results

Documents authored by Li, Baitian

Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?

Abstract

Cite as

Asymptotic Rank Speedup Theorems, Revisited

Abstract

Cite as

Counting Perfect Matchings and Hamiltonian Cycles Faster

Abstract

Cite as

Thanks for your feedback!

Could not send message