Bishnu, Arijit ;
Ghosh, Arijit ;
Mishra, Gopinath ;
Paraashar, Manaswi
Counting and Sampling from Substructures Using Linear Algebraic Queries
Abstract
For an unknown n Γ n matrix A having nonnegative entries, the inner product (IP) oracle takes as inputs a specified row (or a column) of A and a vector π― β ββΏ with nonnegative entries, and returns their inner product. Given two input vectors x and y in ββΏ with nonnegative entries, and an unknown matrix A with nonnegative entries with IP oracle access, we design almost optimal sublinear time algorithms for the following two fundamental matrix problems:
 Find an estimate π³ for the bilinear form x^T A y such that π³ β x^T A y.
 Designing a sampler π΅ for the entries of the matrix A such that β(π΅ = (i,j)) β x_i A_{ij} y_j /(x^T A y), where x_i and y_j are ith and jth coordinate of π± and π² respectively. As special cases of the above results, for any submatrix of an unknown matrix with nonnegative entries and IP oracle access, we can efficiently estimate the sum of the entries of any submatrix, and also sample a random entry from the submatrix with probability proportional to its weight. We will show that the above results imply that if we are given IP oracle access to the adjacency matrix of a graph, with nonnegative weights on the edges, then we can design sublinear time algorithms for the following two fundamental graph problems:
 Estimating the sum of the weights of the edges of an induced subgraph, and
 Sampling edges proportional to their weights from an induced subgraph. We show that compared to the classical local queries (degree, adjacency, and neighbor queries) on graphs, we can get a quadratic speedup if we use IP oracle access for the above two problems.
Apart from the above, we study several matrix problems through the lens of IP oracle, like testing if the matrix is diagonal, symmetric, doubly stochastic, etc. Note that IP oracle is in the class of linear algebraic queries used lately in a series of works by BenEliezer et al. [SODA'08], Nisan [SODA'21], Rashtchian et al. [RANDOM'20], Sun et al. [ICALP'19], and Shi and Woodruff [AAAI'19]. Recently, IP oracle was used by Bishnu et al. [RANDOM'21] to estimate dissimilarities between two matrices.
BibTeX  Entry
@InProceedings{bishnu_et_al:LIPIcs.FSTTCS.2022.8,
author = {Bishnu, Arijit and Ghosh, Arijit and Mishra, Gopinath and Paraashar, Manaswi},
title = {{Counting and Sampling from Substructures Using Linear Algebraic Queries}},
booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
pages = {8:18:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772617},
ISSN = {18688969},
year = {2022},
volume = {250},
editor = {Dawar, Anuj and Guruswami, Venkatesan},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17400},
URN = {urn:nbn:de:0030drops174009},
doi = {10.4230/LIPIcs.FSTTCS.2022.8},
annote = {Keywords: Query complexity, Bilinear form, Uniform sampling, Weighted graphs}
}
14.12.2022
Keywords: 

Query complexity, Bilinear form, Uniform sampling, Weighted graphs 
Seminar: 

42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)

Issue date: 

2022 
Date of publication: 

14.12.2022 