- Algebraic complexity, asymptotic spectra and entanglement polytopes
- Award date
- 23 October 2018
- Number of pages
- Amsterdam: Institute for Logic, Language and Computation
- Document type
- PhD thesis
- Interfacultary Research Institutes
- Institute for Logic, Language and Computation (ILLC)
Matrix rank is multiplicative under the Kronecker product, additive under the direct sum, normalised on identity matrices and non-increasing under multiplying from the left and from the right by any matrices. It is the only real matrix parameter with these properties. Strassen studied the tensor extension: find all maps from k-tensors to the reals that are multiplicative under the tensor Kronecker product, additive under the direct sum, normalised on "identity tensors", and non-increasing under acting with linear maps on the k tensor factors. These maps form the "asymptotic spectrum of k-tensors" and capture the asymptotic relations among tensors, including the asymptotic tensor rank. We give the first explicit construction of an infinite family of elements in the asymptotic spectrum of complex k-tensors, based on information theory and entanglement polytopes. Other results on tensors include an extension of the Coppersmith-Winograd method to higher-order tensors.
In graph theory, as a new instantiation of the abstract theory of asymptotic spectra, we introduce the asymptotic spectrum of graphs, which captures the Shannon capacity, a graph parameter characterizing zero-error communication complexity. Examples of elements in the asymptotic spectrum of graphs are the Lovász theta number and the fractional Haemers bounds.
Finally, we study algebraic branching programs, an algebraic model of computation. Ben-Or and Cleve proved that width-3 abps can compute any polynomial efficiently in the formula size, and Allender and Wang proved that some polynomials cannot be computed by any width-2 abp. We prove that any polynomial can be efficiently approximated by a width-2 abp.
- ILLC dissertation series DS-2018-13.
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.