Optimal query complexity for estimating the trace of a matrix

Karl Wimmer, Yi Wu, Peng Zhang

Given an implicit $n\times n$ matrix $A$ with oracle access $x^{T}Ax$ for any $x\in {\mathbb{R}}^n$, we study the query complexity of randomized algorithms for estimating the trace of…