Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTowards a Geometric Approach to Strassens Asymptotic Rank Conjecture
128
0
0.0
(
0
)
Added by
Fulvio Gesmundo
Publication date
2018
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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 develop a geometric framework for Strassens Asymptotic Rank Conjecture that the asymptotic rank of any tight tensor is minimal. In particular, we determine the dimension of the set of tight tensors. We prove that this dimension equals the dimension of the set of oblique tensors, a less restrictive class introduced by Strassen.
rate research
Read More
We investigate an extension of a lower bound on the Waring (cactus) rank of homogeneous forms due to Ranestad and Schreyer. We show that for particular classes of homogeneous forms, for which a generalization of this method applies, the lower bound extends to the level of border (cactus) rank. The approach is based on recent results on tensor asymptotic rank.
A classical set of birational invariants of a variety are its spaces of pluricanonical forms and some of their canonically defined subspaces. Each of these vector spaces admits a typical metric structure which is also birationally invariant. These vector spaces so metrized will be referred to as the pseudonormed spaces of the original varieties. A fundamental question is the following: given two mildly singular projective varieties with some of the first varietys pseudonormed spaces being isometric to the corresponding ones of the second varietys, can one construct a birational map between them which induces these isometries? In this work a positive answer to this question is given for varieties of general type. This can be thought of as a theorem of Torelli type for birational equivalence.
In 1969, Strassen shocked the world by showing that two n x n matrices could be multiplied in time asymptotically less than $O(n^3)$. While the recursive construction in his algorithm is very clear, the key gain was made by showing that 2 x 2 matrix multiplication could be performed with only 7 multiplications instead of 8. The latter construction was arrived at by a process of elimination and appears to come out of thin air. Here, we give the simplest and most transparent proof of Strassens algorithm that we are aware of, using only a simple unitary 2-design and a few easy lines of calculation. Moreover, using basic facts from the representation theory of finite groups, we use 2-designs coming from group orbits to generalize our construction to all n (although the resulting algorithms arent optimal for n at least 3).
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 give improved separations for the query complexity analogue of the log-approximate-rank conjecture i.e. we show that there are a plethora of total Boolean functions on $n$ input bits, each of which has approximate Fourier sparsity at most $O(n^3)$ and randomized parity decision tree complexity $Theta(n)$. This improves upon the recent work of Chattopadhyay, Mande and Sherif (JACM 20) both qualitatively (in terms of designing a large number of examples) and quantitatively (improving the gap from quartic to cubic). We leave open the problem of proving a randomized communication complexity lower bound for XOR compositions of our examples. A linear lower bound would lead to new and improved refutations of the log-approximate-rank conjecture. Moreover, if any of these compositions had even a sub-linear cost randomized communication protocol, it would demonstrate that randomized parity decision tree complexity does not lift to randomized communication complexity in general (with the XOR gadget).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
