A central problem in mining massive data streams is characterizing which functions of an underlying frequency vector can be approximated efficiently. Given the prevalence of large scale linear algebra problems in machine learning, recently there has been considerable effort in extending this data stream problem to that of estimating functions of a matrix. This setting generalizes classical problems to the analogous ones for matrices. For example, instead of estimating frequent-item counts, we now wish to estimate “frequent-direction” counts. A related example is to estimate norms, which now correspond to estimating a vector norm on the singular values of the matrix. Despite recent efforts, the current understanding for such matrix problems is considerably weaker than that for vector problems. We study a number of aspects of estimating matrix norms in a stream that have not previously been considered: (1) multi-pass algorithms, (2) algorithms that see the underlying matrix one row at a time, and (3) time-efficient algorithms. Our multi-pass and row-order algorithms use less memory than what is provably required in the single-pass and entrywise-update models, and thus give separations between these models (in terms of memory). Moreover, all of our algorithms are considerably faster than previous ones. We also prove a number of lower bounds, and obtain for instance, a near-complete characterization of the memory required of row-order algorithms for estimating Schatten $p$-norms of sparse matrices. We complement our results with numerical experiments.

The recent paper A Quantitative Doignon-Bell-Scarf Theorem by Aliev et al. [ Combinatorica, 37 (2017), pp. 313--332] 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 ${R}^n$. They show that there exists a number $c(n,k)$ such that any polyhedron in $\mathbb{R}^n$ that contains exactly $k$ integer points has a relaxation to at most $c(n,k)$ of its inequalities that will define a new polyhedron with the same integer points. They prove that $c(n,k) = O(k)2^n$. In this paper, we improve the bound asymptotically to be sublinear in $k$, that is, $c(n,k) = o(k) 2^n$. We also provide lower bounds on $c(n,k)$, along with other structural results. For dimension n=2, our upper and lower bounds match to within a constant factor.

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 i1,i2,...,im∈[n] and the goal is to identify the items among [n] that appear frequently in the list. In sub-polynomial space, the strongest guarantee available is the l2 guarantee, which requires finding all items that occur at least ε||ƒ||2 times in the stream, where the vector ƒ∈Rn is the count histogram of the stream with ith coordinate equal to the number of times i appears ƒi:=#{jε[m]:ij=i. The first algorithm to achieve the l2 guarantee was the CountSketch of [11], which requires O(ε-2log n) words of memory and O(log n) update time and is known to be space-optimal if the stream allows for deletions. The recent work of [7] gave an improved algorithm for insertion-only streams, using only O(ε-2logε-1log log n) words of memory. In this work, we give an algorithm BPTree for l2 heavy hitters in insertion-only streams that achieves O(ε-2logε-1) words of memory and O(logε-1) update time, which is the optimal dependence on n and m. In addition, we describe an algorithm for tracking ||ƒ||2 at all times with O(ε-2) memory and update time. Our analyses rely on bounding the expected supremum of a Bernoulli process involving Rademachers with limited independence, which we accomplish via a Dudley-like chaining argument that may have applications elsewhere.

We characterize the streaming space complexity of every symmetric norm l (a norm on ℝ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 ± ε)-approximation to the norm of the stream, for every 0 < ε ≤ 1/2. (The bounds match up to (ε-1 logn) factors.) We further extend those bounds to any large approximation ratio D≥ 1.1, showing that the decrease in space complexity is proportional to D2, and that this factor the best possible. All of the bounds depend on the median of l(x) when x is drawn uniformly from the l2 unit sphere. The same median governs many phenomena in high-dimensional spaces, such as large-deviation bounds and the critical dimension in Dvoretzky's Theorem.

In the Network Flow Interdiction problem, an adversary attacks a network in order to minimize the maximums‐t‐flow. Very little is known about the approximatibility of this problem, despite decades of interest in it. It is, surprisingly, nontrivial to obtain in polynomial time an approximation guarantee that is independent of the number of edges in the graph and their capacities. We present the first such approximation algorithm, which has approximation ratio at most 2(n−1) for any graph withnvertices. We complement the algorithm with a hardness theorem. Past work has shown that Network Flow Interdiction cannot be much easier to approximate than Densestk‐Subgraph. We show that anynϵ‐approximation algorithm for Network Flow Interdiction, or one of several variants, would imply a 2n4ϵ‐approximation algorithm for Densestk‐Subgraph, which is an improvement over past work in terms of the polynomial factor. We also show that Network Flow Interdiction is essentially the same as the Budgeted Minimums‐t‐Cut problem, and transferring our results gives hardness and an approximation algorithm for that problem, as well. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 69(4), 378–387 2017

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 ∑i=1n g(|fi|), where f ∈ Zn 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).

Given a stream p1, …, pm of items from a universe U, which, without loss of generality we identify with the set of integers {1, 2, …, n}, we consider the problem of returning all ℓ2-heavy hitters, i.e., those items j for which fj ≥ є √F2, where fj is the number of occurrences of item j in the stream, and F2 = ∑i ∈ [n] fi2. Such a guarantee is considerably stronger than the ℓ1-guarantee, which finds those j for which fj ≥ є m. In 2002, Charikar, Chen, and Farach-Colton suggested the CountSketch data structure, which finds all such j using Θ(log2 n) bits of space (for constant є > 0). The only known lower bound is Ω(logn) bits of space, which comes from the need to specify the identities of the items found.

Given a stream with frequency vector f in n dimensions, we characterize the space necessary for approximating the frequency negative moments Fp, where p<0, in terms of n, the accuracy, and the L_1 length of the vector f. 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 +/- eps)-approximation to the sum of the coordinates of the vector f transformed by g. 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 +/- eps)-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).