Systematic Data Structure Lower Bounds via the Query-with-Sketch Model

Sumegha Garg, Songhua He, Yuanzhi Li +2

We study data structure lower bounds for the Approximate Matrix Powering (AMP) problem. Given a substochastic, symmetric matrix $\mathbf{M}\in {\mathbb{R}}^{n\times n}$ and parameters…