Search Results

Documents authored by Zhu, Hanlin

Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.26
Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems

Authors: Cyrus Rashtchian, David P. Woodruff, and Hanlin Zhu

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

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.
Cite as

Cyrus Rashtchian, David P. Woodruff, and Hanlin Zhu. Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 26:1-26:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{rashtchian_et_al:LIPIcs.APPROX/RANDOM.2020.26,
  author =	{Rashtchian, Cyrus and Woodruff, David P. and Zhu, Hanlin},
  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 =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.26},
  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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact