1 citations · 1 across the 6 of their papers we have counts for
6 papers
Online Learning with Limited Information in the Sliding Window Model
Vladimir Braverman, Sumegha Garg, Chen Wang +2
Motivated by recent work on the experts problem in the streaming model, we consider the experts problem in the sliding window model. The sliding window model is a well-studied mode…
Tight Lower Bounds for Directed Cut Sparsification and Distributed Min-Cut
Yu Cheng, Max Li, Honghao Lin +3
In this paper, we consider two fundamental cut approximation problems on large graphs. We prove new lower bounds for both problems that are optimal up to logarithmic factors. The f…
Streaming Algorithms with Few State Changes
Rajesh Jayaram, David P. Woodruff, Samson Zhou
In this paper, we study streaming algorithms that minimize the number of changes made to their internal state (i.e., memory contents). While the design of streaming algorithms typi…
A New Information Complexity Measure for Multi-pass Streaming with Applications
Mark Braverman, Sumegha Garg, Qian Li +3
We introduce a new notion of information complexity for multi-pass streaming problems and use it to resolve several important questions in data streams. In the coin problem, one se…
Near-Optimal -Clustering in the Sliding Window Model
David P. Woodruff, Peilin Zhong, Samson Zhou
Clustering is an important technique for identifying structural information in large-scale data analysis, where the underlying dataset may be too large to store. In many applicatio…
Streaming Euclidean -median and -means with Space
Vincent Cohen-Addad, David P. Woodruff, Samson Zhou
We consider the classic Euclidean -median and -means objective on data streams, where the goal is to provide a -approximation to the optimal -median or $k…