25 citations · 76 across the 24 of their papers we have counts for
4 papers · 1 filter
Robust Algorithms on Adaptive Inputs from Bounded Adversaries
Yeshwanth Cherapanamjeri, Sandeep Silwal, David P. Woodruff +3
We study dynamic algorithms robust to adaptive input generated from sources with bounded capabilities, such as sparsity or limited interaction. For example, we consider robust line…
Terminal Embeddings in Sublinear Time
Yeshwanth Cherapanamjeri, Jelani Nelson
Recently (Elkin, Filtser, Neiman 2017) introduced the concept of a {\it terminal embedding} from one metric space to another with a set of designated terminals…
On Adaptive Distance Estimation
Yeshwanth Cherapanamjeri, Jelani Nelson
We provide a static data structure for distance estimation which supports {\it adaptive} queries. Concretely, given a dataset of points in $\mathbb{R}^d…
List Decodable Mean Estimation in Nearly Linear Time
Yeshwanth Cherapanamjeri, Sidhanth Mohanty, Morris Yau
Learning from data in the presence of outliers is a fundamental problem in statistics. Until recently, no computationally efficient algorithms were known to compute the mean of a h…