10 citations · 23 across the 8 of their papers we have counts for
7 papers · 1 filter
Matrix Norms in Data Streams: Faster, Multi-Pass and Row-Order
Vladimir Braverman, Stephen R. Chestnut, Robert Krauthgamer +3
A central problem in data streams is to characterize which functions of an underlying frequency vector can be approximated efficiently. Recently there has been considerable effort…
BPTree: an heavy hitters algorithm using constant memory
Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin +3
The task of finding heavy hitters is one of the best known and well studied problems in the area of data streams. One is given a list and the goal is to…
Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors
Vladimir Braverman, Stephen R. Chestnut, David P. Woodruff +1
A central problem in the theory of algorithms for data streams is to determine which functions on a stream can be approximated in sublinear, and especially sub-polynomial or poly-l…
Hardness and Approximation for Network Flow Interdiction
Stephen R. Chestnut, Rico Zenklusen
In the Network Flow Interdiction problem an adversary attacks a network in order to minimize the maximum s-t-flow. Very little is known about the approximatibility of this problem…
Beating CountSketch for Heavy Hitters in Insertion Streams
Vladimir Braverman, Stephen R. Chestnut, Nikita Ivkin +1
Given a stream of items from a universe , which, without loss of generality we identify with the set of integers , we consider…
Streaming Symmetric Norms via Measure Concentration
Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut +2
We characterize the streaming space complexity of every symmetric norm (a norm on invariant under sign-flips and coordinate-permutations), by relating this space…
Universal sketches for the frequency negative moments and other decreasing streaming sums
Vladimir Braverman, Stephen R. Chestnut
Given a stream with frequencies , for , we characterize the space necessary for approximating the frequency negative moments , where and the s…