We study the problem of estimating the trace of a matrix A that can only be accessed through
matrix-vector multiplication. We introduce a new randomized algorithm, Hutch++, which …

Consider the following gap cycle counting problem in the streaming model: The edges of a 2-
regular n-vertex graph G are arriving one-by-one in a stream and we are promised that G is …

We study iterative methods based on Krylov subspaces for low-rank approximation under
any Schatten-p norm. Here, given access to a matrix A through matrix-vector products, an …

Matrix trace estimation is ubiquitous in machine learning applications and has traditionally
relied on Hutchinson's method, which requires $ O (\log (1/\delta)/\epsilon^ 2) $ matrix-vector …

We consider the problem of rank-1 low-rank approximation (LRA) in the matrix-vector
product model under various Schatten norms: _ ‖ u ‖ _ 2= 1\left ‖ A\left (Iu u …

In Euclidean Uniform Facility Location, the input is a set of clients in R^d and the goal is to
place facilities to serve them, so as to minimize the total cost of opening facilities plus …

We study the problem of estimating the diagonal of an implicitly given matrix $ A $. For such
a matrix we have access to an oracle that allows us to evaluate the matrix vector product …

We study the problem of testing whether a matrix A∈\mathbbR n× n with bounded entries (||
A||∞≤ 1) is positive semidefinite (PSD), or ε-far in Euclidean distance from the PSD cone …

It is known that the Frank-Wolfe (FW) algorithm, which is affine covariant, enjoys faster
convergence rates than $\mathcal {O}\left (1/K\right) $ when the constraint set is strongly …

In this thesis, we explore streaming algorithms for approximating constraint satisfaction
problems (CSPs). The setup is roughly the following: A computer has limited memory space …