License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.26
URN: urn:nbn:de:0030-drops-126294
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12629/
Go to the corresponding LIPIcs Volume Portal

Rashtchian, Cyrus ; Woodruff, David P. ; Zhu, Hanlin

Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems

pdf-format:
LIPIcs-APPROX26.pdf (0.6 MB)

Abstract

We consider the general problem of learning about a matrix through vector-matrix-vector queries. These queries provide the value of u^{T}Mv over a fixed field ? for a specified pair of vectors u,v ∈ ?ⁿ. To motivate these queries, we observe that they generalize many previously studied models, such as independent set queries, cut queries, and standard graph queries. They also specialize the recently studied matrix-vector query model. Our work is exploratory and broad, and we provide new upper and lower bounds for a wide variety of problems, spanning linear algebra, statistics, and graphs. Many of our results are nearly tight, and we use diverse techniques from linear algebra, randomized algorithms, and communication complexity.

BibTeX - Entry

@InProceedings{rashtchian_et_al:LIPIcs:2020:12629,
  author =	{Cyrus Rashtchian and David P. Woodruff and Hanlin Zhu},
  title =	{{Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{26:1--26:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Jaros{\l}aw Byrka and Raghu Meka},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12629},
  URN =		{urn:nbn:de:0030-drops-126294},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.26},
  annote =	{Keywords: Query complexity, property testing, vector-matrix-vector, linear algebra, statistics, graph parameter estimation}
}

Keywords: Query complexity, property testing, vector-matrix-vector, linear algebra, statistics, graph parameter estimation
Collection: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Issue Date: 2020
Date of publication: 11.08.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI