Karl Wimmer

most citedOptimal query complexity for estimating the trace of a matrix

2 citations · 2 across the 2 of their papers we have counts for

collaborators

2 papers

cs.CC2014★ 2 cited

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} A x$ for any $x \in R^{n}$ , we study the query complexity of randomized algorithms for estimating the trace of…

cs.LG2014

Approximate resilience, monotonicity, and the complexity of agnostic learning

Dana Dachman-Soled, Vitaly Feldman, Li-Yang Tan +2

A function $f$ is $d$ -resilient if all its Fourier coefficients of degree at most $d$ are zero, i.e., $f$ is uncorrelated with all low-degree parities. We study the notion of $\mat…