Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userWeighted Slice Rank and a Minimax Correspondence to Strassens Spectra
276
0
0.0
(
0
)
Added by
Jeroen Zuiddam
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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 bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix $M$ as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.
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 resolution, establishing an injective map from the set of irreducible Weyl group representations to simple equivariant perverse sheaves on the nilpotent cone. In this manuscript, we consider a generalization of the Springer resolution using a variety defined by the first author. Our main result shows that in the type A case, applying the decomposition theorem to this map yields all simple perverse sheaves on the nilpotent cone with multiplicity as predicted by Lusztigs generalized Springer correspondence.
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 as computing $f$ to error $epsilon$ on worst-case inputs. Notably, however, the distribution $mu$ depends on the target error level $epsilon$: the hard distribution which is tight for bounded error might be trivial to solve to small bias, and the hard distribution which is tight for a small bias level might be far from tight for bounded error levels. In this work, we introduce a new type of minimax theorem which can provide a hard distribution $mu$ that works for all bias levels at once. We show that this works for randomized query complexity, randomized communication complexity, some randomized circuit models, quantum query and communication complexities, approximate polynomial degree, and approximate logrank. We also prove an improved version of Impagliazzos hardcore lemma. Our proofs rely on two innovations over the classical approach of using Von Neumanns minimax theorem or linear programming duality. First, we use Sions minimax theorem to prove a minimax theorem for ratios of bilinear functions representing the cost and score of algorithms. Second, we introduce a new way to analyze low-bias randomized algorithms by viewing them as forecasting algorithms evaluated by a proper scoring rule. The expected score of the forecasting version of a randomized algorithm appears to be a more fine-grained way of analyzing the bias of the algorithm. We show that such expected scores have many elegant mathematical properties: for example, they can be amplified linearly instead of quadratically. We anticipate forecasting algorithms will find use in future work in which a fine-grained analysis of small-bias algorithms is required.
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}. Dietzfelbinger et al. raised the question if this bound can be achieved, and showed a boolean Hadamard factorization of the identity of rank n^{0.792}. More recently, Klauck and Wolf gave a construction of Hadamard factorizations of the identity of rank n^{0.613}. Over finite fields, Friesen and Theis resolved the question, showing for a prime p and r=p^t+1 a Hadamard factorization of the identity A of size r(r-1)+1 and rank r over F_p. Here we resolve the question for fields of zero characteristic, up to a constant factor, giving a construction of Hadamard factorizations of the identity of rank r and size (r+1)r/2. The matrices in our construction are blockwise Toeplitz, and have entries whose magnitudes are binomial coefficients.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
