Jeroen Zuiddam, PhD student at Centrum Wiskunde & Informatica (CWI), developed new mathematical instruments to study the problem of multiplying large matrices fast. This and other results are the topic of his PhD thesis, ‘Algebraic complexity, asymptotic spectra and entanglement polytopes’, which he defended at the University of Amsterdam on 23 October 2018. For his research he received a 'cum laude' predicate.
Multiplying matrices – arrays of numbers – is an essential part of many basic algorithms. Zuiddam explains: "Matrices are everywhere. Think, for instance, of graphics software for video games, medical images, robot movements, tracking user information, data compression or seismic surveys, to mention just a few examples. Since matrices typically grow very large, it is important to find algorithms that multiply matrices fast. Over the last 50 years, much progress has been made on constructing such algorithms. We do not know, however, whether the theoretical limit has been reached".
Zuiddam continues: "In the eighties the mathematician Strassen introduced a mathematical framework to study this theoretical limit, the ‘asymptotic spectrum of tensors’. Me and my coauthors Matthias Christandl (University of Copenhagen) and Péter Vrana (Budapest University of Technology and Economics) made an interesting discovery in this theory: the first explicit infinite family of elements in the asymptotic spectrum of complex tensors, which we called quantum functionals".
Besides the above work, Zuiddam discovered intriguing connections from Strassen’s theory to the cap set problem in combinatorics – related to the card game Set – and to the problem of communicating over noisy channels efficiently in information theory – the study of Shannon capacity. The results on tensors and the cap set problem were presented at the quantum information theory conference QIP 2018 and the theoretical computer science conference STOC 2018.
The project was carried out in the Algorithms & Complexity research group at CWI, under the supervision of Harry Buhrman (CWI and ILLC/UvA), with funding from the Netherlands Organisation for Scientific Research (NWO) and the European Commission. Jeroen Zuiddam started his PhD at CWI in 2014. Since September 2018, he has been a postdoctoral member in the School of Mathematics at the Institute for Advanced Study, Princeton.
More information
- http://math.ias.edu/~jzuiddam/
- https://www.cwi.nl/research/groups/algorithms-and-complexity
- http://qusoft.org/
- https://www.uva.nl/content/evenementen/promoties/2018/10/algebraische-complexiteit-en-asymptotische-spectra.html?date=23102018&origin=2JGUe3atTn6QrBm737Ylfg
- Promotores: Prof. H.M. Buhrman (CWI, UvA/ILLC, QuSoft), Prof. M. Christandl (Københavns Universitet)
