  We consider algorithms with access to an unknown matrix $M\in\mathbb{F}^{n
\times d}$ via matrix-vector products, namely, the algorithm chooses vectors
$\mathbf{v}^1, \ldots, \mathbf{v}^q$, and observes $M\mathbf{v}^1,\ldots,
M\mathbf{v}^q$. Here the $\mathbf{v}^i$ can be randomized as well as chosen
adaptively as a function of $ M\mathbf{v}^1,\ldots,M\mathbf{v}^{i-1}$.
Motivated by applications of sketching in distributed computation, linear
algebra, and streaming models, as well as connections to areas such as
communication complexity and property testing, we initiate the study of the
number $q$ of queries needed to solve various fundamental problems. We study
problems in three broad categories, including linear algebra, statistics
problems, and graph problems. For example, we consider the number of queries
required to approximate the rank, trace, maximum eigenvalue, and norms of a
matrix $M$; to compute the AND/OR/Parity of each column or row of $M$, to
decide whether there are identical columns or rows in $M$ or whether $M$ is
symmetric, diagonal, or unitary; or to compute whether a graph defined by $M$
is connected or triangle-free. We also show separations for algorithms that are
allowed to obtain matrix-vector products only by querying vectors on the right,
versus algorithms that can query vectors on both the left and the right. We
also show separations depending on the underlying field the matrix-vector
product occurs in. For graph problems, we show separations depending on the
form of the matrix (bipartite adjacency versus signed edge-vertex incidence
matrix) to represent the graph.
  Surprisingly, this fundamental model does not appear to have been studied on
its own, and we believe a thorough investigation of problems in this model
would be beneficial to a number of different application areas.
