اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدInner Product Oracle can Estimate and Sample
59
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Edge estimation problem in unweighted graphs using local and sometimes global queries is a fundamental problem in sublinear algorithms. It has been observed by Goldreich and Ron (Random Structures & Algorithms, 2008), that weighted edge estimation for weighted graphs require $Omega(n)$ local queries, where $n$ denotes the number of vertices in the graph. To handle this problem, we introduce a new inner product query on matrices. Inner product query generalizes and unifies all previously used local queries on graphs used for estimating edges. With this new query, we show that weighted edge estimation in graphs with particular kind of weights can be solved using sublinear queries, in terms of the number of vertices. We also show that using this query we can solve the problem of the bilinear form estimation, and the problem of weighted sampling of entries of matrices induced by bilinear forms. This work is the first step towards weighted edge estimation mentioned in Goldreich and Ron (Random Structures & Algorithms, 2008).
قيم البحث
اقرأ أيضاً
We study the query complexity of quantum learning problems in which the oracles form a group $G$ of unitary matrices. In the simplest case, one wishes to identify the oracle, and we find a description of the optimal success probability of a $t$-query
quantum algorithm in terms of group characters. As an application, we show that $Omega(n)$ queries are required to identify a random permutation in $S_n$. More generally, suppose $H$ is a fixed subgroup of the group $G$ of oracles, and given access to an oracle sampled uniformly from $G$, we want to learn which coset of $H$ the oracle belongs to. We call this problem coset identification and it generalizes a number of well-known quantum algorithms including the Bernstein-Vazirani problem, the van Dam problem and finite field polynomial interpolation. We provide character-theoretic formulas for the optimal success probability achieved by a $t$-query algorithm for this problem. One application involves the Heisenberg group and provides a family of problems depending on $n$ which require $n+1$ queries classically and only $1$ query quantumly.
We develop a notion of {em inner rank} as a tool for obtaining lower bounds on the rank of matrix multiplication tensors. We use it to give a short proof that the border rank (and therefore rank) of the tensor associated with $ntimes n$ matrix multip
lication over an arbitrary field is at least $2n^2-n+1$. While inner rank does not provide improvements to currently known lower bounds, we argue that this notion merits further study.
The tendency of semidefinite programs to compose perfectly under product has been exploited many times in complexity theory: for example, by Lovasz to determine the Shannon capacity of the pentagon; to show a direct sum theorem for non-deterministic
communication complexity and direct product theorems for discrepancy; and in interactive proof systems to show parallel repetition theorems for restricted classes of games. Despite all these examples of product theorems--some going back nearly thirty years--it was only recently that Mittal and Szegedy began to develop a general theory to explain when and why semidefinite programs behave perfectly under product. This theory captured many examples in the literature, but there were also some notable exceptions which it could not explain--namely, an early parallel repetition result of Feige and Lovasz, and a direct product theorem for the discrepancy method of communication complexity by Lee, Shraibman, and Spalek. We extend the theory of Mittal and Szegedy to explain these cases as well. Indeed, to the best of our knowledge, our theory captures all examples of semidefinite product theorems in the literature.
We find a limit formula for a generalization of MacDonalds inner product in finitely many variables, using equivariant localization on the Grassmannian variety, and the main lemma from cite{Car}, which bounds the torus characters of the higher c{C}ec
h cohomology groups. We show that the MacDonald inner product conjecture of type $A$ follows from a special case, and the Pieri rules section of MacDonalds book cite{Mac}, making this limit suitable replacement for the norm squared of one, the usual normalizing constant.
We present inequalities related to generalized matrix function for positive semidefinite block matrices. We introduce partial generalized matrix functions corresponding to partial traces and then provide an unified extension of the recent inequalitie
s due to Choi [6], Lin [14] and Zhang et al. [5,19]. We demonstrate the applications of a positive semidefinite $3times 3$ block matrix, which motivates us to give a simple alternative proof of Dragomirs inequality and Kreins inequality.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
