10 citations · 23 across the 8 of their papers we have counts for
11 papers
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…
Sublinear Bounds for a Quantitative Doignon-Bell-Scarf Theorem
Stephen R. Chestnut, Robert Hildebrand, Rico Zenklusen
The recent paper "A quantitative Doignon-Bell-Scarf Theorem" by Aliev et al. generalizes the famous Doignon-Bell-Scarf Theorem on the existence of integer solutions to systems of 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…
Interdicting Structured Combinatorial Optimization Problems with {0,1}-Objectives
Stephen R. Chestnut, Rico Zenklusen
Interdiction problems ask about the worst-case impact of a limited change to an underlying optimization problem. They are a natural way to measure the robustness of a system, or to…
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…
Counting Spanning Trees of Threshold Graphs
Stephen R. Chestnut, Donniell E. Fishkind
Cayley's formula states that there are spanning trees in the complete graph on vertices; it has been proved in more than a dozen different ways over its 150 year hist…
Occupancy distributions in Markov chains via Doeblin's ergodicity coefficient
Stephen Chestnut, Manuel Lladser
We apply Doeblin's ergodicity coefficient as a computational tool to approximate the occupancy distribution of a set of states in a homogeneous but possibly non-stationary finite M…