Source author record

Stephen R. Chestnut

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms math.OC Discrete Mathematics math.CO

Catalog footprint

Research overview

6works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors

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. Our contribution is to give a condition such that, except for a narrow class of functions $g$ , there is a space-efficient approximation algorithm for the sum if and only if $g$ satisfies the condition. The functions $g$ that we are able to characterize include all convex, concave, monotonic, polynomial, and trigonometric functions, among many others, and is the first such characterization for non-monotonic functions. Thus, for nearly all functions of one variable, we answer the open question from the celebrated paper of Alon, Matias and Szegedy (1996).

preprint2015arXiv

Beating CountSketch for Heavy Hitters in Insertion Streams

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 ε\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$ . Such a guarantee is considerably stronger than the $\ell_1$ -guarantee, which finds those $j$ for which $f_j \geq εm$ . In 2002, Charikar, Chen, and Farach-Colton suggested the {\sf CountSketch} data structure, which finds all such $j$ using $Θ(\log^2 n)$ bits of space (for constant $ε> 0$ ). The only known lower bound is $Ω(\log n)$ bits of space, which comes from the need to specify the identities of the items found. In this paper we show it is possible to achieve $O(\log n \log \log n)$ bits of space for this problem. Our techniques, based on Gaussian processes, lead to a number of other new results for data streams, including (1) The first algorithm for estimating $F_2$ simultaneously at all points in a stream using only $O(\log n\log\log n)$ bits of space, improving a natural union bound and the algorithm of Huang, Tai, and Yi (2014). (2) A way to estimate the $\ell_{\infty}$ norm of a stream up to additive error $ε\sqrt{F_2}$ with $O(\log n\log\log n)$ bits of space, resolving Open Question 3 from the IITK 2006 list for insertion only streams.

preprint2015arXiv

Hardness and Approximation for Network Flow Interdiction

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. In particular, any $n^{o(1)}$ -approximation algorithm for Network Flow Interdiction would imply an $n^{o(1)}$ -approximation algorithm for Densest k-Subgraph. We complement this hardness results with the first approximation algorithm for Network Flow Interdiction, which has approximation ratio 2(n-1). We also show that Network Flow Interdiction is essentially the same as the Budgeted Minimum s-t-Cut problem, and transferring our results gives the first approximation hardness and algorithm for that problem, as well.

preprint2015arXiv

Interdicting Structured Combinatorial Optimization Problems with {0,1}-Objectives

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. Most interdiction problems are NP-hard, and furthermore, even designing efficient approximation algorithms that allow for estimating the order of magnitude of a worst-case impact, has turned out to be very difficult. Not very surprisingly, the few known approximation algorithms are heavily tailored for specific problems. Inspired by an approach of Burch et al. (2003), we suggest a general method to obtain pseudoapproximations for many interdiction problems. More precisely, for any $α>0$ , our algorithm will return either a $(1+α)$ -approximation, or a solution that may overrun the interdiction budget by a factor of at most $1+α^{-1}$ but is also at least as good as the optimal solution that respects the budget. Furthermore, our approach can handle submodular interdiction costs when the underlying problem is to find a maximum weight independent set in a matroid, as for example the maximum weight forest problem. The approach can sometimes be refined by exploiting additional structural properties of the underlying optimization problem to obtain stronger results. We demonstrate this by presenting a PTAS for interdicting $b$ -stable sets in bipartite graphs.

preprint2015arXiv

Universal sketches for the frequency negative moments and other decreasing streaming sums

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$ , $ε$ , 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ε)$ -approximation to $\sum g(|f_d|)$ , where again the sum is over items with nonzero frequency. The storage required is expressed in the form of the solution to a relatively simple nonlinear optimization problem, and the algorithm is universal for $(1\pmε)$ -approximations to any such sum where the applied function is nonnegative, nonincreasing, and has the same or smaller space complexity as $g$ . This partially answers an open question of Nelson (IITK Workshop Kanpur, 2009).

preprint2013arXiv

Counting Spanning Trees of Threshold Graphs

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, ...,n-1$ , of the number of vertices of degree at least $i$ . In this manuscript, we provide a direct combinatorial proof for this formula which does not use the Matrix Tree Theorem; the proof is an extension of Joyal's proof for Cayley's formula. Then we apply this methodology to give a formula for the number of spanning trees in any difference graph.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Stephen R. Chestnut

Research overview

Is this your work?

6 publications

Streaming Space Complexity of Nearly All Functions of One Variable on Frequency Vectors

Beating CountSketch for Heavy Hitters in Insertion Streams

Hardness and Approximation for Network Flow Interdiction

Interdicting Structured Combinatorial Optimization Problems with {0,1}-Objectives

Universal sketches for the frequency negative moments and other decreasing streaming sums

Counting Spanning Trees of Threshold Graphs

See the researcher in context

Building this map preview