48 citations · 60 across the 9 of their papers we have counts for
6 papers · 1 filter
Constant Approximation for Individual Preference Stable Clustering
Anders Aamand, Justin Y. Chen, Allen Liu +4
Individual preference (IP) stability, introduced by Ahmadi et al. (ICML 2022), is a natural clustering objective inspired by stability and fairness constraints. A clustering is …
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…
Streaming Algorithms for Learning with Experts: Deterministic Versus Robust
David P. Woodruff, Fred Zhang, Samson Zhou
In the online learning with experts problem, an algorithm must make a prediction about an outcome on each of days (or times), given a set of experts who make predictions on…
Optimal Query Complexities for Dynamic Trace Estimation
David P. Woodruff, Fred Zhang, Qiuyi Zhang
We consider the problem of minimizing the number of matrix-vector queries needed for accurate trace estimation in the dynamic setting where our underlying matrix is changing slowly…
Faster Fundamental Graph Algorithms via Learned Predictions
Justin Y. Chen, Sandeep Silwal, Ali Vakilian +1
We consider the question of speeding up classic graph algorithms with machine-learned predictions. In this model, algorithms are furnished with extra advice learned from past or si…
Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization
Samuel B. Hopkins, Jerry Li, Fred Zhang
We study the problem of estimating the mean of a distribution in high dimensions when either the samples are adversarially corrupted or the distribution is heavy-tailed. Recent dev…