The Library
Counting and sampling from substructures using linear algebraic queries
Tools
Tools
Tools
Bishnu, Arijit, Ghosh, Arijit, Mishra, Gopinath and Paraashar, Manaswi (2022) Counting and sampling from substructures using linear algebraic queries. In: 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, Chennai, India, 18–20 Dec 2022. Published in: Leibniz International Proceedings in Informatics (LIPIcs), 250 (8). ISBN 9783959772617. doi:10.4230/LIPIcs.FSTTCS.2022.8 ISSN 1868-8969.
|
PDF
WRAP-Counting-and-sampling-from-substructures-using-linear-algebraic-queries-Mishra-2022.pdf - Published Version - Requires a PDF viewer. Available under License Creative Commons Attribution 4.0. Download (860Kb) | Preview |
Official URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2022.8
Abstract
For an unknown n × n matrix A having non-negative entries, the inner product (IP) oracle takes as inputs a specified row (or a column) of A and a vector v E Rⁿ with non-negative entries, and returns their inner product. Given two input vectors x and y in Rⁿ with non-negative entries, and an unknown matrix A with non-negative entries with IP oracle access, we design almost optimal sublinear time algorithms for the following two fundamental matrix problems:
- Find an estimate X for the bilinear form x^T A y such that X ≈ x^T A y.
- Designing a sampler Z for the entries of the matrix A such that P(Z = (i,j)) ≈ x_i A_{ij} y_j /(x^T A y), where x_i and y_j are i-th and j-th coordinate of x and y respectively. As special cases of the above results, for any submatrix of an unknown matrix with non-negative 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 non-negative 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 Ben-Eliezer 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.
| Item Type: | Conference Item (Paper) | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics > QA75 (Please use QA76 Electronic Computers. Computer Science) Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software |
|||||||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | |||||||||
| Library of Congress Subject Headings (LCSH): | Numerical analysis, Bilinear forms , Inner product spaces, Computer algorithms | |||||||||
| Journal or Publication Title: | Leibniz International Proceedings in Informatics (LIPIcs) | |||||||||
| Publisher: | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik | |||||||||
| ISBN: | 9783959772617 | |||||||||
| ISSN: | 1868-8969 | |||||||||
| Official Date: | 14 December 2022 | |||||||||
| Dates: |
|
|||||||||
| Volume: | 250 | |||||||||
| Number: | 8 | |||||||||
| DOI: | 10.4230/LIPIcs.FSTTCS.2022.8 | |||||||||
| Status: | Peer Reviewed | |||||||||
| Publication Status: | Published | |||||||||
| Access rights to Published version: | Open Access (Creative Commons) | |||||||||
| Date of first compliant deposit: | 23 January 2023 | |||||||||
| Date of first compliant Open Access: | 23 January 2023 | |||||||||
| RIOXX Funder/Project Grant: |
|
|||||||||
| Conference Paper Type: | Paper | |||||||||
| Title of Event: | 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science | |||||||||
| Type of Event: | Conference | |||||||||
| Location of Event: | Chennai, India | |||||||||
| Date(s) of Event: | 18–20 Dec 2022 | |||||||||
| Related URLs: | ||||||||||
| Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
