Algebraic complexity, asymptotic spectra and entanglement polytopes

<p> 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. <p> 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. <p> 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.

• View at Worldcat

Full Text ( Final Version , 942kb )