✦ LIBER ✦

The Space Complexity of Approximating the Frequency Moments

✍ Scribed by Noga Alon; Yossi Matias; Mario Szegedy

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 172 KB
Volume: 58
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.1997.1545

No coin nor oath required. For personal study only.

✦ Synopsis

The frequency moments of a sequence containing m i elements of type i, 1 i n, are the numbers F k = n i=1 m k i . We consider the space complexity of randomized algorithms that approximate the numbers F k , when the elements of the sequence are given one by one and cannot be stored. Surprisingly, it turns out that the numbers F 0 , F 1 , and F 2 can be approximated in logarithmic space, whereas the approximation of F k for k 6 requires n 0(1) space. Applications to data bases are mentioned as well.

📜 SIMILAR VOLUMES

Complexity of approximating the oriented

Complexity of approximating the oriented diameter of chordal graphs

✍ Fedor V. Fomin; Martín Matamala; Ivan Rapaport 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB

## Abstract The oriented diameter of a bridgeless connected undirected (__bcu__) graph __G__ is the smallest diameter among all the diameters of strongly connected orientations of __G__. We study algorithmic aspects of determining the oriented diameter of a chordal graph. We (a) construct a linear‐

Approximate Moments of the Adès Distribu

Approximate Moments of the Adès Distribution

✍ Philip Holgate 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 403 KB 👁 1 views

Laplaoe's method of approximating to integrals is need to obtain asymptotic expreaaiona for the central moments, and the momenta about mro, of the Ad& distribution. A correction term for the power law relationehip between the varisnce and the meen is derived.

Weighted Approximation of the Renewal Sp

Weighted Approximation of the Renewal Spacing Processes

✍ P. Barbe 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 315 KB

On the complex moment problem

✍ Yurij M. Berezansky; Mykola E. Dudkin 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB

## Abstract The article is devoted to the solution of the infinite‐dimensional variant of the complex moment problem, and to the uniqueness of the solution. The main approach is illustrated for the best explanation on the one‐dimensional case. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)

Spectral Approximation of the Free-Space

Spectral Approximation of the Free-Space Heat Kernel

✍ Leslie Greengard; Patrick Lin 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 154 KB

Many problems in applied mathematics, physics, and engineering require the solution of the heat equation in unbounded domains. Integral equation methods are particularly appropriate in this setting for several reasons: they are unconditionally stable, they are insensitive to the complexity of the ge

On the Approximation Properties for the

On the Approximation Properties for the Space H∞

✍ Jean Bourgain; Oleg Reinov 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB 👁 1 views

It is unknown whether the HARDY space Hhas the approximation property. However, it will be shown that for each p f 1 Ha has the approximation property AP,, defined below (see also [6]), and, moreover, Hn has the approximation property ''up to log n" (see Theorem 9).