Publications (93)
Transductive and Learning-Augmented Online Regression
Vinod Raman, Shenghao Xie, Samson Zhou
Motivated by the predictable nature of real-life in data streams, we study online regression when the learner has access to predictions about future examples. In the extreme case,…
A Strong Separation for Adversarially Robust Estimation for Linear Sketches
Elena Gribelyuk, Honghao Lin, David P. Woodruff +2
The majority of streaming problems are defined and analyzed in a static setting, where the data stream is any worst-case sequence of insertions and deletions that is fixed in advan…
Learning a Latent Simplex in Input-Sparsity Time
Ainesh Bakshi, Chiranjib Bhattacharyya, Ravi Kannan +2
We consider the problem of learning a latent -vertex simplex , given access to , which can be viewed as a data matrix with …
On the Security of Proofs of Sequential Work in a Post-Quantum World
Jeremiah Blocki, Seunghoon Lee, Samson Zhou
A Proof of Sequential Work (PoSW) allows a prover to convince a resource-bounded verifier that the prover invested a substantial amount of sequential time to perform some underlyin…
Better Bounds for the Distributed Experts Problem
David P. Woodruff, Samson Zhou
In this paper, we study the distributed experts problem, where experts are distributed across servers for timesteps. The loss of each expert at each time is the $\e…
On the Price of Differential Privacy for Hierarchical Clustering
Chengyuan Deng, Jie Gao, Jalaj Upadhyay +2
Hierarchical clustering is a fundamental unsupervised machine learning task with the aim of organizing data into a hierarchy of clusters. Many applications of hierarchical clusteri…