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

arXiv: https://arxiv.org/abs/2006.14015 · HTML: https://mlsanity.com/paper/2006.14015/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Jun 2020.

## Built on by (most cited first, 8 of 8)

- [Query lower bounds for log-concave sampling](https://mlsanity.com/paper/2304.02599/) (2023)
- [Low-Rank Approximation with 1/ε1/3 Matrix-Vector Products](https://mlsanity.com/paper/2202.05120/) (2022)
- [Average-Case Communication Complexity of Statistical Problems](https://mlsanity.com/paper/2107.01335/) (2021)
- [Krylov Methods are (nearly) Optimal for Low-Rank Approximation](https://mlsanity.com/paper/2304.03191/) (2023)
- [Even Faster Kernel Matrix Linear Algebra via Density Estimation](https://mlsanity.com/paper/2510.02540/) (2025)
- [Non-PSD Matrix Sketching with Applications to Regression and Optimization](https://mlsanity.com/paper/2106.08544/) (2021)
- [Query Efficient Structured Matrix Learning](https://mlsanity.com/paper/2507.19290/) (2025)
- [Prior Knowledge Makes It Possible: From Sublinear Graph Algorithms to LLM Test-Time Methods](https://mlsanity.com/paper/2510.16609/) (2025)

## Abstract (arXiv)

We consider the general problem of learning about a matrix through vector-matrix-vector queries. These queries provide the value of boldsymboluTboldsymbolMboldsymbolv over a fixed field mathbbF for a specified pair of vectors boldsymbolu,boldsymbolv ∈ mathbbFn. 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.