162,033 research outputs found
Subrank and Optimal Reduction of Scalar Multiplications to Generic Tensors
Get PDFSince the seminal works of Strassen and Valiant it has been a central theme in algebraic complexity theory to understand the relative complexity of algebraic problems, that is, to understand which algebraic problems (be it bilinear maps like matrix multiplication in Strassen’s work, or the determinant and permanent polynomials in Valiant’s) can be reduced to each other (under the appropriate notion of reduction).
In this paper we work in the setting of bilinear maps and with the usual notion of reduction that allows applying linear maps to the inputs and output of a bilinear map in order to compute another bilinear map. As our main result we determine precisely how many independent scalar multiplications can be reduced to a given bilinear map (this number is called the subrank, and extends the concept of matrix diagonalization to tensors), for essentially all (i.e. generic) bilinear maps. Namely, we prove for a generic bilinear map T : V × V → V where dim(V) = n that θ(√n) independent scalar multiplications can be reduced to T. Our result significantly improves on the previous upper bound from the work of Strassen (1991) and Bürgisser (1990) which was n^{2/3 + o(1)}. Our result is very precise and tight up to an additive constant. Our full result is much more general and applies not only to bilinear maps and 3-tensors but also to k-tensors, for which we find that the generic subrank is θ(n^{1/(k-1)}). Moreover, as an application we prove that the subrank is not additive under the direct sum.
The subrank plays a central role in several areas of complexity theory (matrix multiplication algorithms, barrier results) and combinatorics (e.g., the cap set problem and sunflower problem). As a consequence of our result we obtain several large separations between the subrank and tensor methods that have received much interest recently, notably the slice rank (Tao, 2016), analytic rank (Gowers-Wolf, 2011; Lovett, 2018; Bhrushundi-Harsha-Hatami-Kopparty-Kumar, 2020), geometric rank (Kopparty-Moshkovitz-Zuiddam, 2020), and G-stable rank (Derksen, 2020).
Our proofs of the lower bounds rely on a new technical result about an optimal decomposition of tensor space into structured subspaces, which we think may be of independent interest
Discreteness of asymptotic tensor ranks
Get PDFTensor parameters that are amortized or regularized over large tensor powers, often called “asymp-
totic” tensor parameters, play a central role in several areas including algebraic complexity theory
(constructing fast matrix multiplication algorithms), quantum information (entanglement cost and
distillable entanglement), and additive combinatorics (bounds on cap sets, sunflower-free sets,
etc.). Examples are the asymptotic tensor rank, asymptotic slice rank and asymptotic subrank.
Recent works (Costa–Dalai, Blatter–Draisma–Rupniewski, Christandl–Gesmundo–Zuiddam) have
investigated notions of discreteness (no accumulation points) or “gaps” in the values of such tensor
parameters.
We prove a general discreteness theorem for asymptotic tensor parameters of order-three tensors
and use this to prove that (1) over any finite field (and in fact any finite set of coefficients in any
field), the asymptotic subrank and the asymptotic slice rank have no accumulation points, and (2)
over the complex numbers, the asymptotic slice rank has no accumulation points.
Central to our approach are two new general lower bounds on the asymptotic subrank of tensors,
which measures how much a tensor can be diagonalized. The first lower bound says that the
asymptotic subrank of any concise three-tensor is at least the cube-root of the smallest dimension.
The second lower bound says that any concise three-tensor that is “narrow enough” (has one
dimension much smaller than the other two) has maximal asymptotic subrank.
Our proofs rely on new lower bounds on the maximum rank in matrix subspaces that are obtained
by slicing a three-tensor in the three different directions. We prove that for any concise tensor, the
product of any two such maximum ranks must be large, and as a consequence there are always two
distinct directions with large max-rank
Quantum asymptotic spectra of graphs and non-commutative graphs, and quantum Shannon capacities
Get PDFWe study quantum versions of the Shannon capacity of graphs and non-commutative graphs. We introduce the asymptotic spectrum of graphs with respect to quantum homomorphisms and entanglement-assisted homomorphisms, and we introduce the asymptotic spectrum of non-commutative graphs with respect to entanglement-assisted homomorphisms. We apply Strassen's spectral theorem (J. Reine Angew. Math., 1988) and obtain dual characterizations of the corresponding Shannon capacities and asymptotic preorders in terms of their asymptotic spectra. This work extends the study of the asymptotic spectrum of graphs initiated by Zuiddam (Combinatorica, 2019) to the quantum domain. We study the relations among the three new quantum asymptotic spectra and the asymptotic spectrum of graphs. The bounds on the several Shannon capacities that have appeared in the literature we fit into the corresponding quantum asymptotic spectra. In particular, we prove that the (fractional) complex Haemers bound upper bounds the quantum Shannon capacity, defined as the regularization of the quantum independence number (Mančinska and Roberson, J. Combin. Theory Ser. B, 2016), which leads to a separation with the Lovász theta function
[Report to Chief J. E. Curry, by an unknown author #1]
No full textReport to Chief J. E. Curry, by an unknown author. The report contains a list of officers who gave depositions to the United States Attorney
[Report to Chief J. E. Curry, by an unknown author #2]
No full textReport to Chief J. E. Curry, by an unknown author. The report contains a list of officers who gave depositions to the United States Attorney
The next gap in the subrank of 3-tensors
Get PDFRecent works of Costa–Dalai, Christandl–Gesmundo–Zuiddam, Blatter–Draisma–Rupniewski, and Briët–Christandl–Leigh–Shpilka–Zuiddam have investigated notions of discreteness and gaps in the possible values that asymptotic tensor ranks can take. In particular, it was shown that the asymptotic subrank and asymptotic slice rank of any nonzero 3-tensor is equal to 1, equal to 1.88, or at least 2 (over any field), and that the set of possible values of these parameters is discrete (in several regimes). We determine exactly the next gap, showing that the asymptotic subrank and asymptotic slice rank of any nonzero 3-tensor is equal to 1, equal to 1.88, equal to 2, or at least 2.68
The asymptotic induced matching number of hypergraphs: Balanced binary strings
Get PDFWe compute the asymptotic induced matching number of the k-partite k-uniform hypergraphs whose edges are the k-bit strings of Hamming weight k/2, for any large enough even number k. Our lower bound relies on the higher-order extension of the well-known Coppersmith–Winograd method from algebraic complexity theory, which was proven by Christandl, Vrana and Zuiddam. Our result is motivated by the study of the power of this method as well as of the power of the Strassen support functionals (which provide upper bounds on the asymptotic induced matching number), and the connections to questions in tensor theory, quantum information theory and theoretical computer science. Our proof relies on a new combinatorial inequality that may be of independent interest. This inequality concerns how many pairs of Boolean vectors of fixed Hamming weight can have their sum in a fixed subspace.</p
Quantum asymptotic spectra of graphs and non-commutative graphs, and quantum Shannon capacities
Get PDFWe study quantum versions of the Shannon capacity of graphs and non-commutative graphs. We introduce the asymptotic spectrum of graphs with respect to quantum and entanglement-assisted homomorphisms, and we introduce the asymptotic spectrum of non-commutative graphs with respect to entanglement-assisted homomorphisms. We apply Strassen’s spectral theorem (J. Reine Angew. Math., 1988) in order to obtain dual characterizations of the corresponding Shannon capacities and asymptotic preorders in terms of their asymptotic spectra. This work extends the study of the asymptotic spectrum of graphs initiated by Zuiddam (Combinatorica, 2019) to the quantum domain. We then exhibit spectral points in the new quantum asymptotic spectra and discuss their relations with the asymptotic spectrum of graphs. In particular, we prove that the (fractional) real and complex Haemers bounds upper bound the quantum Shannon capacity, which is defined as the regularization of the quantum independence number (Mančinska and Roberson, J. Combin. Theory Ser. B, 2016), and that the fractional real and complex Haemers bounds are elements in the quantum asymptotic spectrum of graphs. This is in contrast to the Haemers bounds defined over certain finite fields, which can be strictly smaller than the quantum Shannon capacity. Moreover, since the Haemers bound can be strictly smaller than the Lovász theta function (Haemers, IEEE Trans. Inf. Theory, 1979), we find that the quantum Shannon capacity and the Lovász theta function do not coincide. As a consequence, two well-known conjectures in quantum information theory, namely: 1) the entanglement-assisted zero-error capacity of a classical channel is equal to the Lovász theta function and 2) maximally entangled states and projective measurements are sufficient to achieve the entanglement-assisted zero-error capacity, cannot both be true
Geometric rank of tensors and subrank of matrix multiplication
Get PDFMotivated by problems in algebraic complexity theory (e.g., matrix
multiplication) and extremal combinatorics (e.g., the cap set problem and the
sunflower problem), we introduce the geometric rank as a new tool in the study
of tensors and hypergraphs. We prove that the geometric rank is an upper bound
on the subrank of tensors and the independence number of hypergraphs. We prove
that the geometric rank is smaller than the slice rank of Tao, and relate
geometric rank to the analytic rank of Gowers and Wolf in an asymptotic
fashion. As a first application, we use geometric rank to prove a tight upper
bound on the (border) subrank of the matrix multiplication tensors, matching
Strassen's well-known lower bound from 1987
On Algebraic Branching Programs of Small Width
Get PDFIn 1979 Valiant showed that the complexity class VP_e of families with polynomially bounded formula size is contained in the class VP_s of families that have algebraic branching programs (ABPs) of polynomially bounded size. Motivated by the problem of separating these classes we study the topological closure VP_e-bar, i.e. the class of polynomials that can be approximated arbitrarily closely by polynomials in VP_e. We describe VP_e-bar with a strikingly simple complete polynomial (in characteristic different from 2) whose recursive definition is similar to the Fibonacci numbers. Further understanding this polynomial seems to be a promising route to new formula lower bounds.
Our methods are rooted in the study of ABPs of small constant width. In 1992 Ben-Or and Cleve showed that formula size is polynomially equivalent to width-3 ABP size. We extend their result (in characteristic different from 2) by showing that approximate formula size is polynomially equivalent to approximate width-2 ABP size. This is surprising because in 2011 Allender and Wang gave explicit polynomials that cannot be computed by width-2 ABPs at all! The details of our construction lead to the aforementioned characterization of VP_e-bar.
As a natural continuation of this work we prove that the class VNP can be described as the class of families that admit a hypercube summation of polynomially bounded dimension over a product of polynomially many affine linear forms. This gives the first separations of algebraic complexity classes from their nondeterministic analogs
- …
