The @math 'th frequency moment of a sequence of integers is defined as @math , where @math is the number of times that @math occurs in the sequence. Here we study the quantum complexity of approximately computing the frequency moments in two settings. In the query complexity setting, we wish to minimise the number of queries to the input used to approximate @math up to relative error @math . We give quantum algorithms which outperform the best possible classical algorithms up to quadratically. In the multiple-pass streaming setting, we see the elements of the input one at a time, and seek to minimise the amount of storage space, or passes over the data, used to approximate @math . We describe quantum algorithms for @math , @math and @math in this model which outperform the best possible classical algorithms almost quadratically.
( @math , @math ) Alon, Matias and Szegedy gave single-pass streaming algorithms using space @math @cite_35 . An almost-optimal @math algorithm was later given by Indyk and Woodruff for any @math @cite_11 . This was simplified by , who also improved the dependence on @math @cite_22 . Very recently, gave an @math algorithm for @math and @math @cite_18 . This effectively matches the tightest known general space lower bound on @math -pass streaming algorithms, @math shown by Woodruff and Zhang @cite_32 .
@cite_35 @cite_18 @cite_22 @cite_32 @cite_11
2950256099 2055900608 2044334960 2160681854
We consider the unweighted bipartite maximum matching problem in the one-pass turnstile streaming model where the input stream consists of edge insertions and deletions. In the insertion-only model, a one-pass @math -approximation streaming algorithm can be easily obtained with space @math , where @math denotes the number of vertices of the input graph. We show that no such result is possible if edge deletions are allowed, even if space @math is granted, for every @math . Specifically, for every @math , we show that in the one-pass turnstile streaming model, in order to compute a @math -approximation, space @math is required for constant error randomized algorithms, and, up to logarithmic factors, space @math is sufficient. Our lower bound result is proved in the simultaneous message model of communication and may be of independent interest. At [email protected]?10, Agarwal and Sharathkumar presented a streaming algorithm for approximating the minimum enclosing ball of a set of points in d-dimensional Euclidean space. Their algorithm requires one pass, uses O(d) space, and was shown to have approximation factor at most (1+3) [email protected] 1.3661. We prove that the same algorithm has approximation factor less than 1.22, which brings us much closer to a (1+2) 2 1.207 lower bound given by Agarwal and Sharathkumar. We also apply this technique to the dynamic version of the minimum enclosing ball problem (in the non-streaming setting). We give an O(dn)-space data structure that can maintain a 1.22-approximate minimum enclosing ball in O(dlogn) expected amortized time per insertion deletion. We investigate the importance of space when solving problems based on graph distance in the streaming model. In this model, the input graph is presented as a stream of edges in an arbitrary order. The main computational restriction of the model is that we have limited space and therefore cannot store all the streamed data; we are forced to make space-efficient summaries of the data as we go along. For a graph of n vertices and m edges, we show that testing many graph properties, including connectivity (ergo any reasonable decision problem about distances) and bipartiteness, requires Ω(n) bits of space. Given this, we then investigate how the power of the model increases as we relax our space restriction. Our main result is an efficient randomized algorithm that constructs a (2t + 1)-spanner in one pass. With high probability, it uses O(t .n1+1 t log2n) bits of space and processes each edge in the stream in O(t2·n1 t log n) time. We find approximations to diameter and girth via the constructed spanner. For t = Ω(log n log log n), the space requirement of the algorithm is O(n .polylog n), and the per-edge processing time is O(polylog n). We also show a corresponding lower bound of t for the approximation ratio achievable when the space restriction is O(t.n1+1 t log2n).We then consider the scenario in which we are allowed multiple passes over the input stream. Here, we investigate whether allowing these extra passes will compensate for a given space restriction. We show that finding vertices at distance d from a particular vertex will always take d passes, for all d ∈ 1,...,t 2 , when the space restriction is o(n1+1 t). For girth, we show the existence of a direct trade-off between space and passes in the form of a lower bound on the product of the space requirement and number of passes. Finally, we conclude with two general techniques for speeding up the per-edge computation time of streaming algorithms while increasing the space by at most a log factor. We prove that any one-pass streaming algorithm which (e, Δ)-approximates the kth frequency moment F k , for any real k ≠ 1 and any e = Ω(1 √m), must use Ω(1 e²) bits of space, where m is the size of the universe. This is optimal in terms of e, resolves the open questions of Bar- in [3, 4], and extends the Ω(1 e²) lower bound for F 0 in [11] to much smaller e by applying novel techniques. Along the way we lower bound the one-way communication complexity of approximating the Hamming distance and the number of bipartite graphs with minimum maximum degree constraints.