NDLI: Zero-one frequency laws

Please wait, while we are loading the content...

Spectral methods for matrices and tensors

Are many small sets explicitly small?

Message passing algorithms: a success looking for theoreticians

Perfect matchings in o(n log n) time in regular bipartite graphs

How to compress interactive communication

Load balancing and orientability thresholds for random hypergraphs

A full characterization of quantum advice

Public-key cryptography from different assumptions

Detecting high log-densities: an $O(n^{¼})$ approximation for densest k-subgraph

Improving exhaustive search implies superpolynomial lower bounds

Recognizing well-parenthesized expressions in the streaming model

Improved algorithms for computing fisher's market clearing prices: computing fisher's market clearing prices

A sparse Johnson: Lindenstrauss transform

A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations

Budget constrained auctions with heterogeneous items

On the list-decodability of random linear codes

The limits of buffering: a tight lower bound for dynamic membership in the external memory model

The HOM problem is decidable

Optimal bounds for sign-representing the intersection of two halfspaces by polynomials

Augmenting undirected node-connectivity by one

Changing base without losing space

Bilipschitz snowflakes and metrics of negative type

Deterministic identity testing of depth-4 multilinear circuits with bounded top fan-in

A shorter proof of the graph minor algorithm: the unique linkage theorem

Graph expansion and the unique games conjecture

Interactive privacy via the median mechanism

Erratum for: on basing one-way functions on NP-hardness

Extensions and limits to vertex sparsification

A strong direct product theorem for disjointness

Combinatorial approach to the interpolation method and scaling limits in sparse random graphs

BQP and the polynomial hierarchy

Oblivious RAMs without cryptogrpahic assumptions

Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth

On the complexity of circuit satisfiability

Measuring independence of datasets

Bayesian algorithmic mechanism design

Saving space by algebraization

Sorting under partial information (without the ellipsoid algorithm)

On the searchability of small-world networks with arbitrary underlying structure

Local list-decoding and testing of random linear codes from high error

Maintaining a large matching and a small vertex cover

Complexity theory for operators in analysis

Bounding the average sensitivity and noise sensitivity of polynomial threshold functions

Towards polynomial lower bounds for dynamic problems

Approximations for the isoperimetric and spectral profile of graphs and related parameters

Tensor-rank and lower bounds for arithmetic formulas

Odd cycle packing

On the complexity of #CSP

The price of privately releasing contingency tables and the spectra of random matrices with correlated rows

Subgraph sparsification and nearly optimal ultrasparsifiers

Hardness amplification in proof complexity

The maximum multiflow problems with bounded fractionality

A quantum lovász local lemma

On the round complexity of covert computation

Optimal homologous cycles, total unimodularity, and linear programming

Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses

Zero-one frequency laws

Multi-parameter mechanism design and sequential posted pricing

On the structure of cubic and quartic polynomials

Matroid matching: the power of local search

Almost tight bounds for rumour spreading with conductance

Pseudorandom generators for polynomial threshold functions

Connectivity oracles for failure prone graphs

Solving polynomial equations in smoothed polynomial time and a near solution to smale's 17th problem

An invariance principle for polytopes

An improved LP-based approximation for steiner tree

An optimal ancestry scheme and small universal posets

Weighted geometric set cover via quasi-uniform sampling

Non-commutative circuits and the sum-of-squares problem

On the geometry of differential privacy

Tractable hypergraph properties for constraint satisfaction and conjunctive queries

Privacy amplification with asymptotically optimal entropy loss

Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms

Near-optimal extractors against quantum storage

Efficiency improvements in constructing pseudorandom generators from one-way functions

Approximate sparse recovery: optimizing time and measurements

Distributed computation in dynamic networks

Efficiently learning mixtures of two Gaussians

On the hardness of the noncommutative determinant

Differential privacy under continual observation

Conditional hardness of precedence constrained scheduling on identical machines

Zero-one frequency laws

Content Provider	ACM Digital Library
Author	Braverman, Vladimir Ostrovsky, Rafail
Abstract	Data streams emerged as a critical model for multiple applications that handle vast amounts of data. One of the most influential and celebrated papers in streaming is the "AMS" paper on computing frequency moments by Alon, Matias and Szegedy. The main question left open (and explicitly asked) by AMS in 1996 is to give the precise characterization for which functions G on frequency vectors $m_{i}$ (1≤ i ≤ n) can Σi∈ [n] $G(m_{i})$ be approximated efficiently, where "efficiently" means by a single pass over data stream and poly-logarithmic memory. No such characterization was known despite a tremendous amount of research on frequency-based functions in streaming literature. In this paper we finally resolve the AMS main question and give a precise characterization (in fact, a zero-one law) for all monotonically increasing functions on frequencies that are zero at the origin. That is, we consider all monotonic functions G: R → R such that G(0) = 0 and G can be computed in poly-logarithmic time and space and ask, for which G in this class is there an (1±ε)-approximation algorithm for computing Σi∈ [n] $G(m_{i})$ for any polylogarithmic ε? We give an algebraic characterization for all such G so that: For all functions G in our class that satisfy our algebraic condition, we provide a very general and constructive way to derive an efficient (1±ε)-approximation algorithm for computing Σi∈ [n] $G(m_{i})$ with polylogarithmic memory and a single pass over data stream; while: For all functions G in our class that do not satisfy our algebraic characterization, we show a lower bound that requires greater then polylog memory for computing an approximation to Σi∈ [n] $G(m_{i})$ by any one-pass streaming algorithm. Thus, we provide a zero-one law for all monotonically increasing functions G which are zero at the origin. Our results are quite general. As just one illustrative example, our main theorem implies a lower bound for G(x) $=(x(x-1))^{0.5arctan(x+1)},$ while for a function G(x) $=(x(x+1))^{0.5arctan(x+1)}$ our main theorem automatically yields a polylog memory one-pass (1±ε)-approximation algorithm for computing Σi∈ [n] $G(m_{i}).$ For both of these examples no lower or upper bounds were known. Of course, these are just illustrative examples, and there are many others. One might argue that these two functions may not be of interest in practical applications -- we stress that our law works for all functions in this class, and the above examples illustrate the power of our method. To the best of our knowledge, this is the first zero-one law in the streaming model for a wide class of functions, though we suspect that there are many more such laws to be discovered. Surprisingly, our upper bound requires only 4-wise independence and does not need the stronger machinery of Nisan's pseudorandom generators, even though our class captures multiple functions that previously required Nisan's generators. Furthermore, we believe that our methods can be extended to the more general models and complexity classes. For instance, the law also holds for a smaller class of non-decreasing and symmetric functions (i.e., G(x) = G(-x) and G(0) = 0) which, due to negative values, allow deletions.
Starting Page	281
Ending Page	290
Page Count	10
File Format	PDF
ISBN	9781450300506
DOI	10.1145/1806689.1806729
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2010-06-05
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Theory of computation Randomized algorithms Data streams
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in