13 citations · 13 across the 5 of their papers we have counts for
5 papers
Lower Bounds for Differential Privacy Under Continual Observation and Online Threshold Queries
Edith Cohen, Xin Lyu, Jelani Nelson +2
One of the most basic problems for studying the "price of privacy over time" is the so called private counter problem, introduced by Dwork et al. (2010) and Chan et al. (2010). In…
Hardness of Low Rank Approximation of Entrywise Transformed Matrix Products
Tamas Sarlos, Xingyou Song, David Woodruff +2
Inspired by fast algorithms in natural language processing, we study low rank approximation in the entrywise transformed setting where we want to find a good rank approximation…
FAVOR#: Sharp Attention Kernel Approximations via New Classes of Positive Random Features
Valerii Likhosherstov, Krzysztof Choromanski, Avinava Dubey +3
The problem of efficient approximation of a linear operator induced by the Gaussian or softmax kernel is often addressed using random features (RFs) which yield an unbiased approxi…
Tricking the Hashing Trick: A Tight Lower Bound on the Robustness of CountSketch to Adaptive Inputs
Edith Cohen, Jelani Nelson, Tamás Sarlós +1
CountSketch and Feature Hashing (the "hashing trick") are popular randomized dimensionality reduction methods that support recovery of -heavy hitters (keys where $v_i^2…
Fastfood: Approximate Kernel Expansions in Loglinear Time
Quoc Viet Le, Tamas Sarlos, Alexander Johannes Smola
Despite their successes, what makes kernel methods difficult to use in many large scale problems is the fact that storing and computing the decision function is typically expensive…