ﻻ يوجد ملخص باللغة العربية
Structural and computational understanding of tensors is the driving force behind faster matrix multiplication algorithms, the unraveling of quantum entanglement, and the breakthrough on the cap set problem. Strassens asymptotic spectra program (SFCS 1986) characterizes optimal matrix multiplication algorithms through monotone functionals. Our work advances and makes novel connections among two recent developments in the study of tensors, namely (1) the slice rank of tensors, a notion of rank for tensors that emerged from the resolution of the cap set problem (Ann. of Math. 2017), and (2) the quantum functionals of tensors (STOC 2018), monotone functionals defined as optimizations over moment polytopes. More precisely, we introduce an extension of slice rank that we call weighted slice rank and we develop a minimax correspondence between the asymptotic weighted slice rank and the quantum functionals. Weighted slice rank encapsulates different notions of bipartiteness of quantum entanglement. The correspondence allows us to give a rank-type characterization of the quantum functionals. Moreover, whereas the original definition of the quantum functionals only works over the complex numbers, this new characterization can be extended to all fields. Thereby, in addition to gaining deeper understanding of Strassens theory for the complex numbers, we obtain a proposal for quantum functionals over other fields. The finite field case is crucial for combinatorial and algorithmic problems where the field can be optimized over.
We make a first geometric study of three varieties in $mathbb{C}^m otimes mathbb{C}^m otimes mathbb{C}^m$ (for each $m$), including the Zariski closure of the set of tight tensors, the tensors with continuous regular symmetry. Our motivation is to de
Positive semidefinite rank (PSD-rank) is a relatively new quantity with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bo
The Springer resolution of the nilpotent cone is used to give a geometric construction of the irreducible representations of Weyl groups. Borho and MacPherson obtain the Springer correspondence by applying the decomposition theorem to the Springer re
The celebrated minimax principle of Yao (1977) says that for any Boolean-valued function $f$ with finite domain, there is a distribution $mu$ over the domain of $f$ such that computing $f$ to error $epsilon$ against inputs from $mu$ is just as hard a
Say that A is a Hadamard factorization of the identity I_n of size n if the entrywise product of A and the transpose of A is I_n. It can be easily seen that the rank of any Hadamard factorization of the identity must be at least sqrt{n}. Dietzfelbing