Sampling algorithms: lower bounds and applications

DOI10.1145/380752.380810MaRDI QIDQ5175979zbMATH OpenOpenAlexFDO

Authors Ziv Bar-Yossef, Ravi Kumar, D. Sivakumar

Publication date 27 February 2015

Published in Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/380752.380810

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Statistical sampling theory and related topics (62D99)

Recommendations

• Lower bounds for sampling algorithms for estimating the average
• Sampling lower bounds via information theory
• A sample of samplers: a computational perspective on sampling
• An information statistics approach to data stream and communication complexity
• scientific article; zbMATH DE number 2083809

Cites work

• A constant-factor approximation algorithm for the \(k\)-median problem (extended abstract)

Cited in

(35)

• Hamming weight proofs of proximity with one-sided error
• On computing minimal independent support and its applications to sampling and counting
• Sampling algorithms.
• Range partitioning within sublinear time: algorithms and lower bounds
• Sampling algorithms for estimating the mean of bounded random variables
• Optimal sampling from sliding windows
• Adversary lower bounds for nonadaptive quantum algorithms
• Book Reviews
• Non-interactive proofs of proximity
• Sublinear algorithms in the external memory model
• On Unifying the Space of ℓ₀-Sampling Algorithms
• On adaptive sampling
• A Constant Factor Approximation Algorithm for Event-Based Sampling
• Sampling to provide or to bound: With applications to fully dynamic graph algorithms
• Sampling for approximating R-limited functions
• Three theorems regarding testing graph properties
• Sublinear algorithms for approximating string compressibility
• Strong lower bounds for approximating distribution support size and the distinct elements problem
• Range partitioning within sublinear time in the external memory model
• The complexity of distributions
• Submodular Approximation: Sampling-based Algorithms and Lower Bounds
• Streaming techniques and data aggregation in networks of tiny artefacts
• On the power of two-point based sampling
• Stochastic streams: sample complexity vs. space complexity
• The query complexity of estimating weighted averages
• A sample of samplers: a computational perspective on sampling
• An automatic inequality prover and instance optimal identity testing
• scientific article; zbMATH DE number 2083809 (Why is no real title available?)
• A simple analysis of the error probability of two-point based sampling
• Sampling lower bounds via information theory
• Predicting winner and estimating margin of victory in elections using sampling
• Time hierarchies for sampling distributions
• Time hierarchies for sampling distributions
• Sample complexity of the distinct elements problem
• On the randomness complexity of efficient sampling

This page was built for publication: Sampling algorithms: lower bounds and applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5175979)