3 papers
cs.DS2026
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…
cs.LG2026
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…
cs.DS2025
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…