12 papers
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: , , $Î(C_{13})\geq6.302455083464\ldot…
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…
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…
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…
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…