Inner Product Oracle can Estimate and Sample
share
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 Ω(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).
READ FULL TEXT