Shenghao Xie

collaborators

6 papers

cs.DS2026

Adversarially Robust Streaming Algorithms for $(k, z)$ -Clustering

Chengzhi Guo, Shaofeng H. C. Jiang, Robert Krauthgamer +3

We design adversarially robust algorithms for dynamic geometric streams that $(1 + ε)$ -approximate $k$ -Median and $k$ -Means in Euclidean space $R^{d}$ , using $\tilde{O}(kd \…

cs.DS2025

$L_{p}$ Sampling in Distributed Data Streams with Applications to Adversarial Robustness

Honghao Lin, Zhao Song, David P. Woodruff +2

In the distributed monitoring model, a data stream over a universe of size $n$ is distributed over $k$ servers, who must continuously provide certain statistics of the overall data…

cs.DS2025

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams

Vincent Cohen-Addad, David P. Woodruff, Shenghao Xie +1

We study the problem of graph and hypergraph sparsification in insertion-only data streams. The input is a hypergraph $H = (V, E, w)$ with $n$ nodes, $m$ hyperedges, and rank $r$ , an…

cs.LG2025

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,…

cs.LG2025

Towards Sampling Data Structures for Tensor Products in Turnstile Streams

Zhao Song, Shenghao Xie, Samson Zhou

This paper studies the computational challenges of large-scale attention-based models in artificial intelligence by utilizing importance sampling methods in the streaming setting.…

cs.DS2025

Perfect Sampling in Turnstile Streams Beyond Small Moments

David P. Woodruff, Shenghao Xie, Samson Zhou

Given a vector $x \in R^{n}$ induced by a turnstile stream $S$ , a non-negative function $G : R \to R$ , a perfect $G$ -sampler outputs an index $i$ with proba…

Adversarially Robust Streaming Algorithms for (k,z)-Clustering

Lp​ Sampling in Distributed Data Streams with Applications to Adversarial Robustness

Nearly Space-Optimal Graph and Hypergraph Sparsification in Insertion-Only Data Streams

Transductive and Learning-Augmented Online Regression

Towards Sampling Data Structures for Tensor Products in Turnstile Streams

Perfect Sampling in Turnstile Streams Beyond Small Moments

Adversarially Robust Streaming Algorithms for $(k, z)$ -Clustering

$L_{p}$ Sampling in Distributed Data Streams with Applications to Adversarial Robustness