Stephen R. Chestnut

Stephen R. Chestnut
Are you Stephen R. Chestnut?

Claim your profile, edit publications, add additional information:

Contact Details

Stephen R. Chestnut

Pubs By Year

Pub Categories

Computer Science - Data Structures and Algorithms (8)
Mathematics - Optimization and Control (3)
Computer Science - Discrete Mathematics (2)
Quantitative Biology - Genomics (1)
Mathematics - Combinatorics (1)
Mathematics - Probability (1)

Publications Authored By Stephen R. Chestnut

We design new sketching algorithms for unitarily invariant matrix norms, including the Schatten $p$-norms~$\|{\cdot}\|_{S_p}$, and obtain, as a by-product, streaming algorithms that approximate the norm of a matrix $A$ presented as a turnstile data stream. The primary advantage of our streaming algorithms is that they are simpler and faster than previous algorithms, while requiring the same or less storage. Our three main results are a faster sketch for estimating $\|{A}\|_{S_p}$, a smaller-space $O(1)$-pass sketch for $\|{A}\|_{S_p}$, and more general sketching technique that yields sublinear-space approximations for a wide class of matrix norms. Read More

The task of finding heavy hitters is one of the best known and well studied problems in the area of data streams. In sub-polynomial space, the strongest guarantee available is the $\ell_2$ guarantee, which requires finding all items that occur at least $\varepsilon\|f\|_2$ times in the stream, where the $i$th coordinate of the vector $f$ is the number of occurrences of $i$ in the stream. The first algorithm to achieve the $\ell_2$ guarantee was the CountSketch of [CCF04], which for constant $\varepsilon$ requires $O(\log n)$ words of memory and $O(\log n)$ update time, and is known to be space-optimal if the stream allows for deletions. Read More

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-logarithmic, space. Given a function $g$, we study the space complexity of approximating $\sum_{i=1}^n g(|f_i|)$, where $f\in\mathbb{Z}^n$ is the frequency vector of a turnstile stream. This is a generalization of the well-known frequency moments problem, and previous results apply only when $g$ is monotonic or has a special functional form. Read More

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 linear inequalities. Their generalization examines the number of facets of a polyhedron that contains exactly $k$ integer points in $\mathbb{R}^n$. Read More

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 identify its weakest spots. Interdiction problems have been studied for a wide variety of classical combinatorial optimization problems, including maximum $s$-$t$ flows, shortest $s$-$t$ paths, maximum weight matchings, minimum spanning trees, maximum stable sets, and graph connectivity. Read More

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 despite decades of interest in it. We present the first approximation hardness, showing that Network Flow Interdiction and several of its variants cannot be much easier to approximate than Densest k-Subgraph. Read More

We characterize the streaming space complexity of every symmetric norm $l$ (a norm on $\mathbb{R}^n$ invariant under sign-flips and coordinate-permutations), by relating this space complexity to the measure-concentration characteristics of $l$. Specifically, we provide nearly matching upper and lower bounds on the space complexity of calculating a $(1\pm\epsilon)$-approximation to the norm of the stream, for every $0<\epsilon\leq 1/2$. (The bounds match up to $poly(\epsilon^{-1} \log n)$ factors. Read More

Given a stream $p_1, \ldots, p_m$ of items from a universe $\mathcal{U}$, which, without loss of generality we identify with the set of integers $\{1, 2, \ldots, n\}$, we consider the problem of returning all $\ell_2$-heavy hitters, i.e., those items $j$ for which $f_j \geq \epsilon \sqrt{F_2}$, where $f_j$ is the number of occurrences of item $j$ in the stream, and $F_2 = \sum_{i \in [n]} f_i^2$. Read More

Given a stream with frequencies $f_d$, for $d\in[n]$, we characterize the space necessary for approximating the frequency negative moments $F_p=\sum |f_d|^p$, where $p<0$ and the sum is taken over all items $d\in[n]$ with nonzero frequency, in terms of $n$, $\epsilon$, and $m=\sum |f_d|$. To accomplish this, we actually prove a much more general result. Given any nonnegative and nonincreasing function $g$, we characterize the space necessary for any streaming algorithm that outputs a $(1\pm\epsilon)$-approximation to $\sum g(|f_d|)$, where again the sum is over items with nonzero frequency. Read More

Cayley's formula states that there are $n^{n-2}$ spanning trees in the complete graph on $n$ vertices; it has been proved in more than a dozen different ways over its 150 year history. The complete graphs are a special case of threshold graphs, and using Merris' Theorem and the Matrix Tree Theorem, there is a strikingly simple formula for counting the number of spanning trees in a threshold graph on $n$ vertices; it is simply the product, over $i=2,3, .. Read More

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 Markov chain. Our approximation is based on new properties satisfied by this coefficient, which allow us to approximate a chain of duration n by independent and short-lived realizations of an auxiliary homogeneous Markov chain of duration of order ln(n). Our approximation may be particularly useful when exact calculations via first-step methods or transfer matrices are impractical, and asymptotic approximations may not be yet reliable. Read More