Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems
This work addresses a foundational problem in query-based learning for matrices, impacting multiple domains like linear algebra and graph theory, but it is exploratory and broad rather than incremental.
The paper tackles the problem of learning about a matrix using vector-matrix-vector queries, which generalize various existing query models, and provides new upper and lower bounds for problems in linear algebra, statistics, and graphs, with many results being nearly tight.
We consider the general problem of learning about a matrix through vector-matrix-vector queries. These queries provide the value of $\boldsymbol{u}^{\mathrm{T}}\boldsymbol{M}\boldsymbol{v}$ over a fixed field $\mathbb{F}$ for a specified pair of vectors $\boldsymbol{u},\boldsymbol{v} \in \mathbb{F}^n$. 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.