Research
My research is on various topics in computational complexity theory, quantum information theory and discrete mathematics.
A unifying theme in my work is the interaction between amortization, symmetry and approximation.
Among the topics that I am particularly interested in are: fast matrix multiplication, Shannon capacity of graphs, the algebraic version of the P versus NP problem, parallel repetition problems, direct sum theorems and Ramsey type problems. I use methods from diverse fields, including representation theory, algebraic geometry, information theory, optimization and real semi-algebraic geometry.
Publications
-
Amortized Circuit Complexity, Formal Complexity Measures, and Catalytic Algorithms
Robert Robere and Jeroen Zuiddam
2021
Oxford-Warwick complexity meetings, 25 February 2021 meeting website
-
Communication Complexity, Corner-Free Sets and the Symmetric Subrank of Tensors
Matthias Christandl, Omar Fawzi, Hoang Ta and Jeroen Zuiddam
2021
-
Weighted slice rank and a minimax correspondence to Strassen's spectra arxiv
Matthias Christandl, Vladimir Lysikov and Jeroen Zuiddam
2020
-
Border rank non-additivity for higher order tensors arxiv
Matthias Christandl, Fulvio Gesmundo, Mateusz Michałek and Jeroen Zuiddam
SIAM Journal on Matrix Analysis and Applications, 2021
-
Barriers for rectangular matrix multiplication arXiv eccc
Matthias Christandl, François Le Gall, Vladimir Lysikov and Jeroen Zuiddam
2020
-
Geometric rank of tensors and subrank of matrix multiplication arXiv eccc proceedings
Swastik Kopparty, Guy Moshkovitz and Jeroen Zuiddam
CCC, 2020 slides video
-
The asymptotic induced matching number of hypergraphs: balanced binary strings arXiv journal
Srinivasan Arunachalam, Péter Vrana and Jeroen Zuiddam
Electronic Journal of Combinatorics, 2020
-
Barriers for fast matrix multiplication from irreversibility arXiv proceedings
Matthias Christandl, Péter Vrana and Jeroen Zuiddam
CCC, 2019 slides
Theory of Computing, 2020
-
Quantum asymptotic spectra of graphs and non-commutative graphs, and quantum Shannon capacities arXiv journal
Yinan Li and Jeroen Zuiddam
IEEE Transactions on Information Theory, 2021
-
The asymptotic spectrum of graphs and the Shannon capacity arXiv journal
Jeroen ZuiddamCombinatorica, 2019
-
Universal points in the asymptotic spectrum of tensors arXiv proceedings
Matthias Christandl, Péter Vrana and Jeroen Zuiddam
QIP, 2018 slides
STOC, 2018 slides
-
Tensor rank is not multiplicative under the tensor product arXiv journal Matthias Christandl, Asger Kjærulff Jensen and Jeroen ZuiddamLinear Algebra and its Applications, 2018
-
The border support rank of two-by-two matrix multiplication is seven arXiv journal Markus Bläser, Matthias Christandl and Jeroen Zuiddam
Chicago Journal of Theoretical Computer Science, 2018
-
On algebraic branching programs of small width arXiv eccc proceedings journal
Karl Bringmann, Christian Ikenmeyer and Jeroen Zuiddam
CCC, 2017 slides
Journal of the ACM, 2018
-
Asymptotic tensor rank of graph tensors: beyond matrix multiplication arXiv journal
Matthias Christandl, Péter Vrana and Jeroen ZuiddamComputational complexity, 2018
-
On the orthogonal rank of Cayley graphs and impossibility of quantum round elimination arXiv journal
Jop Briët and Jeroen Zuiddam
Quantum Information and Computation, 2017
-
Tensor surgery and tensor rank arXiv journal
Matthias Christandl and Jeroen ZuiddamComputational complexity, 2018
-
Clean quantum and classical communication protocols arXiv journal Harry Buhrman, Matthias Christandl, Christopher Perry and Jeroen ZuiddamPhysical Review Letters, 2016
-
Nondeterministic quantum communication complexity: the cyclic equality game and iterated matrix multiplication arXiv proceedings
Harry Buhrman, Matthias Christandl and Jeroen ZuiddamITCS, 2017
-
A note on the gap between rank and border rank arXiv journalJeroen ZuiddamLinear Algebra and its Applications, 2017
PhD thesis
Algebraic complexity, asymptotic spectra and entanglement polytopes, University of Amsterdam,
October 2018 pdf
Recent Talks
- Tensor Tools for Problems in Combinatorics and Complexity, UCSD Theory seminar, 4 January 2021 seminar website
- Tensor Tools for Problems in Combinatorics and Complexity, 2020 Junior Theorists Workshop, Northwestern University, 17 December 2020 workshop website
- Extremal Combinatorics, Tensor Scaling, Moment Polytopes, From Euclidean to Geodesic Convex Optimization reading group, University of Amsterdam, 2 October 2020 reading group website
- Combinatorics, Tensors and Geometry, Texas A&M University, 5 August 2020
- Geometric Rank of Tensors, Seminar series on recent progress in geometric complexity theory, Chennai Mathematical Institute, 17 June 2020
- Geometric Rank of Tensors, Centrum Wiskunde & Informatica, 13 May 2020 slides
- The asymptotic spectrum of graphs: duality for Shannon capacity, NYU theoretical computer science seminar, 21 May 2019 seminar website
- (1) Asymptotic spectra and (2) Inequalities among symmetric polynomials on the unit cube, Mathematics of Quantum Information Theory workshop, Lorentz center Leiden, 6–10 May 2019 workshop website
- The asymptotic spectrum of graphs: duality for Shannon capacity, Rutgers Discrete Mathematics Seminar, 29 April 2019 seminar website
- The asymptotic spectrum of graphs: duality for Shannon capacity, Princeton discrete mathematics seminar, 7 March 2019 seminar website
- Asymptotic spectra, Complexity Theory workshop, Oberwolfach, November 2018 report
- Asymptotic spectra and applications, CSDM seminar, Institute for Advanced Study, October 2018
(Notes: Part I Part II;
Video: Short Part I Part II)
- Asymptotic spectra of tensors and graphs: matrix multiplication exponent and Shannon capacity, Monday Lectures, Facets of complexity, Technische Universität Berlin, 9 July 2018 seminar website
- The asymptotic spectrum of tensors, Dutch Mathematical Congress 2018, Royal Dutch Mathematical Society slides