4 papers
Sublinear Spectral Clustering Oracle with Little Memory
Ranran Shen, Xiaoyi Zhu, Pan Peng +1
We study the problem of designing \emph{sublinear spectral clustering oracles} for well-clusterable graphs. Such an oracle is an algorithm that, given query access to the adjacency…
Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Bandits
Ruiyuan Huang, Zicheng Lyu, Xiaoyi Zhu +1
We study stochastic multi-armed bandits under simultaneous constraints on space and adaptivity: the learner interacts with the environment in batches and has only bits of p…
Simple and Optimal Algorithms for Heavy Hitters and Frequency Moments in Distributed Models
Zengfeng Huang, Zhongzheng Xiong, Xiaoyi Zhu +1
We consider the problems of distributed heavy hitters and frequency moments in both the coordinator model and the distributed tracking model (also known as the distributed function…
Space Complexity of Euclidean Clustering
Xiaoyi Zhu, Yuxiang Tian, Lingxiao Huang +1
The -Clustering problem in Euclidean space has been extensively studied. Given the scale of data involved, compression methods for the Euclidean -Clu…