2 citations · 4 across the 4 of their papers we have counts for
Showing 2014Show all
2 papers · 1 filter
cs.CC2014★ 2 cited
Optimal query complexity for estimating the trace of a matrix
Karl Wimmer, Yi Wu, Peng Zhang
Given an implicit matrix with oracle access for any , 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 is -resilient if all its Fourier coefficients of degree at most are zero, i.e., is uncorrelated with all low-degree parities. We study the notion of $\mat…