Sampling lower bounds via information theory
From MaRDI portal
Publication:3581272
DOI10.1145/780542.780593zbMath1192.94073OpenAlexW2159958017MaRDI QIDQ3581272
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
Analysis of algorithms and problem complexity (68Q25) Measures of information, entropy (94A17) Sampling theory in information and communication theory (94A20)
Related Items (7)
Sampling subproblems of heterogeneous Max-Cut problems and approximation algorithms ⋮ Optimal sampling from sliding windows ⋮ Bounds on the minimax rate for estimating a prior over a VC class from independent learning tasks ⋮ Range partitioning within sublinear time: algorithms and lower bounds ⋮ Sampling based succinct matrix approximation ⋮ Predicting winner and estimating margin of victory in elections using sampling ⋮ Space-efficient estimation of statistics over sub-sampled streams
This page was built for publication: Sampling lower bounds via information theory
