Matrix Queries for Solving Linear Algebra, Statistics, and Graph Problems
Cyrus Rashtchian (UC San Diego)
Monday October 26 2-3pm
Abstract: Over the past several years, there has been much work on solving matrix or graph problems in various query models. For example, edge-probe queries reveal a single entry, while vector-matrix-vector queries return the value of <u, Mv> when u and v are the query vectors and M is the unknown matrix. To get started, I'll discuss new upper and lower bounds for a few problems, such as deciding if a matrix is a permutation or not. Then, I'll talk about recent work that explores statistical-computational trade-offs in streaming, sketching, and query-based models. In this context, I'll present new results on the planted clique problem, where the lower bounds have connections to average-case communication complexity. Many mysteries remain open about the relative query complexity in different models.
Joint work with David P. Woodruff, Peng Ye, and Hanlin Zhu; part of the talk based on our paper that appeared at RANDOM 2020:
https://arxiv.org/abs/2006.14015
To get a taste, you can also watch this animated video that I made:
https://www.youtube.com/watch?v=NVOE1KFNZDo