Sampling lower bounds via information theory

DOI10.1145/780542.780593MaRDI QIDQ3581272zbMATH OpenOpenAlexFDO

Authors Ziv Bar-Yossef

Publication date 16 August 2010

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

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Measures of information, entropy (94A17) Sampling theory in information and communication theory (94A20)

Recommendations

• Sampling algorithms: lower bounds and applications
• Lower bounds for sampling algorithms for estimating the average
• Oracle lower bounds for stochastic gradient sampling algorithms
• An information statistics approach to data stream and communication complexity
• Estimating the unseen, an \(n/\log(n)\)-sample estimator for entropy and support size, shown optimal via new CLTs

Cited in

(10)

• Range partitioning within sublinear time: algorithms and lower bounds
• Predicting winner and estimating margin of victory in elections using sampling
• Space-efficient estimation of statistics over sub-sampled streams
• Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms
• Optimal sampling from sliding windows
• Sampling algorithms: lower bounds and applications
• Sampling, Metric Entropy, and Dimensionality Reduction
• Sample-based distance-approximation for subsequence-freeness
• Lower bounds for sampling algorithms for estimating the average
• Sampling based succinct matrix approximation

This page was built for publication: Sampling lower bounds via information theory

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