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

arXiv: https://arxiv.org/abs/1601.07473 · HTML: https://mlsanity.com/paper/1601.07473/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jan 2016.

## Built on by (most cited first, 1 of 1)

- [Single Pass Entrywise-Transformed Low Rank Approximation](https://mlsanity.com/paper/2107.07889/) (2021)

## Abstract (arXiv)

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