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

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

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

(36)

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

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)