63 citations · 185 across the 32 of their papers we have counts for
34 papers
Concise tensors with maximal symmetries
Annika Holtrup, Jeroen Zuiddam
Conner, Gesmundo, Landsberg and Ventura (2019) determined the largest stabilizer dimension of concise tensors that are binding, and they determined the corresp…
Lean-verified lower bounds for the Shannon capacity of odd cycles
Pjotr Buys, Sven Polak, Jeroen Zuiddam
We give new lower bounds for the Shannon capacities of small odd cycles: , , ,…
Border subrank of higher order tensors and algebras
Chia-Yu Chang, Fulvio Gesmundo, Jeroen Zuiddam
We determine the border subrank of higher order structure tensors of several families of algebras, and in particular obtain the following results. (1) We determine tight bounds on…
Universality of asymptotic graph homomorphism
Anna Luchnikov, Jim Wittebol, Jeroen Zuiddam
The Shannon capacity of graphs, introduced by Shannon in 1956 to model zero-error communication, asks for determining the rate of growth of independent sets in strong powers of gra…
Computing moment polytopes -- with a focus on tensors, entanglement and matrix multiplication
Maxim van den Berg, Matthias Christandl, Vladimir Lysikov +3
Tensors are fundamental in mathematics, computer science, and physics. Their study through algebraic geometry and representation theory has proved very fruitful in the context of a…
A group-theoretic approach to Shannon capacity of graphs and a limit theorem from lattice packings
Pjotr Buys, Sven Polak, Jeroen Zuiddam
We develop a group-theoretic approach to the Shannon capacity problem. Using this approach we extend and recover, in a structured and unified manner, various families of previously…
Explicit non-free tensors
Maxim van den Berg, Matthias Christandl, Vladimir Lysikov +3
Free tensors are tensors which, after a change of bases, have free support: any two distinct elements of its support differ in at least two coordinates. They play a distinguished r…
The moment polytope of matrix multiplication is not maximal
Maxim van den Berg, Matthias Christandl, Vladimir Lysikov +3
Moment polytopes of tensors, the study of which is deeply rooted in invariant theory, representation theory and symplectic geometry, have found relevance in numerous places, from q…
Asymptotic tensor rank is characterized by polynomials
Matthias Christandl, Koen Hoeberechts, Harold Nieuwboer +2
Asymptotic tensor rank is notoriously difficult to determine. Indeed, determining its value for the matrix multiplication tensor would determine the matrix multiplicati…
The asymptotic spectrum distance, graph limits, and the Shannon capacity
David de Boer, Pjotr Buys, Jeroen Zuiddam
Determining the Shannon capacity of graphs is a long-standing open problem in information theory, graph theory and combinatorial optimization. Over decades, a wide range of upper a…
The next gap in the subrank of 3-tensors
Fulvio Gesmundo, Jeroen Zuiddam
Recent works of Costa-Dalai, Christandl-Gesmundo-Zuiddam, Blatter-Draisma-Rupniewski, and Briët-Christandl-Leigh-Shpilka-Zuiddam have investigated notions of discreteness and gaps…
Discreteness of asymptotic tensor ranks
Jop Briët, Matthias Christandl, Itai Leigh +2
Tensor parameters that are amortized or regularized over large tensor powers, often called "asymptotic" tensor parameters, play a central role in several areas including algebraic…
A Gap in the Subrank of Tensors
Matthias Christandl, Fulvio Gesmundo, Jeroen Zuiddam
The subrank of tensors is a measure of how much a tensor can be ''diagonalized''. This parameter was introduced by Strassen to study fast matrix multiplication algorithms in algebr…
Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors
Harm Derksen, Visu Makam, Jeroen Zuiddam
Since the seminal works of Strassen and Valiant it has been a central theme in algebraic complexity theory to understand the relative complexity of algebraic problems, that is, to…
Larger Corner-Free Sets from Combinatorial Degenerations
Matthias Christandl, Omar Fawzi, Hoang Ta +1
There is a large and important collection of Ramsey-type combinatorial problems, closely related to central problems in complexity theory, that can be formulated in terms of the as…
Symmetric Subrank of Tensors and Applications
Matthias Christandl, Omar Fawzi, Hoang Ta +1
Strassen (Strassen, J. Reine Angew. Math., 375/376, 1987) introduced the subrank of a tensor as a natural extension of matrix rank to tensors. Subrank measures the largest diagonal…
Weighted slice rank and a minimax correspondence to Strassen's spectra
Matthias Christandl, Vladimir Lysikov, Jeroen Zuiddam
Structural and computational understanding of tensors is the driving force behind faster matrix multiplication algorithms, the unraveling of quantum entanglement, and the breakthro…
Border rank non-additivity for higher order tensors
Matthias Christandl, Fulvio Gesmundo, Mateusz Michałek +1
Whereas matrix rank is additive under direct sum, in 1981 Schönhage showed that one of its generalizations to the tensor setting, tensor border rank, can be strictly subadditive fo…
Barriers for rectangular matrix multiplication
Matthias Christandl, François Le Gall, Vladimir Lysikov +1
We study the algorithmic problem of multiplying large matrices that are rectangular. We prove that the method that has been used to construct the fastest algorithms for rectangular…
Geometric rank of tensors and subrank of matrix multiplication
Swastik Kopparty, Guy Moshkovitz, Jeroen Zuiddam
Motivated by problems in algebraic complexity theory (e.g., matrix multiplication) and extremal combinatorics (e.g., the cap set problem and the sunflower problem), we introduce th…
The asymptotic induced matching number of hypergraphs: balanced binary strings
Srinivasan Arunachalam, Péter Vrana, Jeroen Zuiddam
We compute the asymptotic induced matching number of the -partite -uniform hypergraphs whose edges are the -bit strings of Hamming weight , for any large enough even…
Barriers for fast matrix multiplication from irreversibility
Matthias Christandl, Péter Vrana, Jeroen Zuiddam
Determining the asymptotic algebraic complexity of matrix multiplication, succinctly represented by the matrix multiplication exponent , is a central problem in algebraic comple…
Quantum asymptotic spectra of graphs and non-commutative graphs, and quantum Shannon capacities
Yinan Li, Jeroen Zuiddam
We study quantum versions of the Shannon capacity of graphs and non-commutative graphs. We introduce the asymptotic spectrum of graphs with respect to quantum and entanglement-assi…
The asymptotic spectrum of graphs and the Shannon capacity
Jeroen Zuiddam
We introduce the asymptotic spectrum of graphs and apply the theory of asymptotic spectra of Strassen (J. Reine Angew. Math. 1988) to obtain a new dual characterisation of the Shan…