NDLI: Tight bounds for distributed functional monitoring

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

Faster approximate multicommodity flow using quadratically coupled flows

Quantum money from hidden subspaces

The cell probe complexity of dynamic range counting

Polyhedral clinching auctions and the adwords polytope

Computing a nonnegative matrix factorization -- provably

Short proofs for the determinant identities

Solution of the propeller conjecture in $R^{3}$

From irreducible representations to locally decodable codes

Approximation algorithms for semi-random partitioning problems

Prior-free auctions with ordered bidders

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates

Fast matrix rank algorithms and applications

Jacobian hits circuits: hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits

The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme

Learning poisson binomial distributions

Competitive contagion in networks

Pseudorandom generators with long stretch and low locality from random local one-way functions

Routing in undirected graphs with constant congestion

Catching the k-NAESAT threshold

Tight bounds for distributed functional monitoring

A complementary pivot algorithm for markets under separable, piecewise-linear concave utilities

Monotone expansion

Multi-way spectral partitioning and higher-order cheeger inequalities

On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption

When the cut condition is enough: a complete characterization for multiflow problems in series-parallel networks

Certifiable quantum dice: or, true random number generation secure against quantum adversaries

Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds

Matroid prophet inequalities

On identity testing of tensors, low-rank recovery and compressed sensing

Time-space tradeoffs in resolution: superpolynomial lower bounds for superlinear space

2log1-ε n hardness for the closest vector problem with preprocessing

Folded codes from function field towers and improved optimal rate list decoding

A near-linear time ε-approximation algorithm for geometric bipartite matching

On the limits of black-box reductions in mechanism design

Tight bounds for monotone switching networks via fourier analysis

Nearly optimal sparse fourier transform

Separating multilinear branching programs and formulas

On vertex sparsifiers with Steiner nodes

Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces

Finding red balloons with split contracts: robustness to individuals' selfishness

Characterizing pseudoentropy and simplifying pseudorandom generator constructions

Improving christofides' algorithm for the s-t path TSP

Complexity of counting CSP with complex weights

Global computation in a poorly connected world: fast rumor spreading with no dependence on conductance

Rational proofs

Nearly complete graphs decomposable into large induced matchings and their applications

Many sparse cuts via higher eigenvalues

Multiparty computation secure against continual memory leakage

Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives

Span programs for functions with constant-sized 1-certificates: extended abstract

Online matching with concave returns

Structure theorem and isomorphism test for graphs with excluded topological subgraphs

On the virtue of succinct proofs: amplifying communication complexity hardness to time-space trade-offs in proof complexity

A new point of NP-hardness for unique games

Subspace evasive sets

Using petal-decompositions to build a low stretch spanning tree

Budget feasible mechanism design: from prior-free to bayesian

Interactive information complexity

Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars

Reconstruction of depth-4 multilinear circuits with top fan-in 2

Approximation algorithms and hardness of integral concurrent flow

Making polynomials robust to noise

An analysis of one-dimensional schelling segregation

Design extractors, non-malleable condensers and privacy amplification

Multiplying matrices faster than coppersmith-winograd

The freezing threshold for k-colourings of a random graph

Tight time-space tradeoff for mutual exclusion

Minimax option pricing meets black-scholes in the limit

Probabilistic existence of rigid combinatorial structures

Approximating the exponential, the lanczos method and an Õ(m)-time spectral algorithm for balanced separator

Beating randomized response on incoherent matrices

Determinism versus nondeterminism with arithmetic tests and computation: extended abstract

Hypercontractivity, sum-of-squares proofs, and their applications

Edge transitive ramanujan graphs and symmetric LDPC good codes

Improved smoothed analysis of multiobjective optimization

An algorithmic characterization of multi-dimensional mechanisms

The multiparty communication complexity of set disjointness

Optimal online buffer scheduling for block devices

Affine projections of polynomials: extended abstract

Robust satisfiability of constraint satisfaction problems

A tight RMR lower bound for randomized mutual exclusion

A quantitative gibbard-satterthwaite theorem without neutrality

From query complexity to computational complexity

Matroids and integrality gaps for hypergraphic steiner tree relaxations

Unconditional differentially private mechanisms for linear queries

Strict fibonacci heaps

Optimal private halfspace counting via discrepancy

Tight lower bounds for the online labeling problem

Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels

Tight bounds for distributed functional monitoring

Content Provider	ACM Digital Library
Author	Zhang, Qin Woodruff, David P.
Abstract	We resolve several fundamental questions in the area of distributed functional monitoring, initiated by Cormode, Muthukrishnan, and Yi (SODA, 2008), and receiving recent attention. In this model there are k sites each tracking their input streams and communicating with a central coordinator. The coordinator's task is to continuously maintain an approximate output to a function computed over the union of the k streams. The goal is to minimize the number of bits communicated. Let the p-th frequency moment be defined as $F_{p}$ = $∑_{i}$ $f_{i}^{p},$ where $f_{i}$ is the frequency of element i. We show the randomized communication complexity of estimating the number of distinct elements (that is, $F_{0})$ up to a 1+ε factor is $Ω(k/ε^{2}),$ improving upon the previous Ω(k + $1/ε^{2})$ bound and matching known upper bounds. For $F_{p},$ p > 1, we improve the previous Ω(k + $1/ε^{2})$ communication bound to $Ω(k^{p-1}/ε^{2}).$ We obtain similar improvements for heavy hitters, empirical entropy, and other problems. Our lower bounds are the first of any kind in distributed functional monitoring to depend on the product of k and $1/ε^{2}.$ Moreover, the lower bounds are for the static version of the distributed functional monitoring model where the coordinator only needs to compute the function at the time when all k input streams end; surprisingly they almost match what is achievable in the (dynamic version of) distributed functional monitoring model where the coordinator needs to keep track of the function continuously at any time step. We also show that we can estimate $F_{p},$ for any p > 1, using $O(k^{p-1}$ $poly(ε^{-1}))$ communication. This drastically improves upon the previous $O(k^{2p+1}N^{1-2/p}$ $poly(ε^{-1}))$ bound of Cormode, Muthukrishnan, and Yi for general p, and their $O(k^{2}/ε$ + $k^{1.5}/ε^{3})$ bound for p = 2. For p = 2, our bound resolves their main open question. Our lower bounds are based on new direct sum theorems for approximate majority, and yield improvements to classical problems in the standard data stream model. First, we improve the known lower bound for estimating $F_{p},$ p > 2, in t passes from $Ω(n^{1-2/p}/(ε^{2/p}$ t)) to $Ω(n^{1-2/p}/(ε^{4/p}$ t)), giving the first bound that matches what we expect when p = 2 for any constant number of passes. Second, we give the first lower bound for estimating $F_{0}$ in t passes with $Ω(1/(ε^{2}$ t)) bits of space that does not use the hardness of the gap-hamming problem.
Starting Page	941
Ending Page	960
Page Count	20
File Format	PDF MP4
ISBN	9781450312455
DOI	10.1145/2213977.2214063
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2012-05-19
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Heavy hitters Quantiles Data streams Distributed functional monitoring Entropy Frequency moments
Content Type	Audio 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