Lower bounds for sampling algorithms for estimating the average

DOI10.1016/0020-0190(94)00171-TMaRDI QIDQ674290zbMATH OpenFDO

Authors Ran Canetti, Guy Even, Oded Goldreich

Publication date 28 February 1997

Published in Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

Lower boundsRandomnessSamplingTheory of computationEstimating

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• A sample of samplers: a computational perspective on sampling
• Sampling algorithms: lower bounds and applications
• Sampling lower bounds via information theory
• Sampling algorithms for estimating the mean of bounded random variables

Cites work

• scientific article; zbMATH DE number 3320868 (Why is no real title available?)
• Lower bounds for sampling algorithms for estimating the average
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• Monte-Carlo approximation algorithms for enumeration problems
• Private vs. common random bits in communication complexity
• Probability Inequalities for Sums of Bounded Random Variables
• Tiny families of functions with random properties: a quality-size trade-off for hashing (preliminary version)

Cited in

(22)

• Sampling lower bounds via information theory
• Sampling algorithms for estimating the mean of bounded random variables
• Metric-distortion bounds under limited information
• Introduction to testing graph properties
• Introduction to testing graph properties
• Testing graph blow-up
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• The query complexity of estimating weighted averages
• Learning distributions by their density levels: A paradigm for learning without a teacher
• Lower bounds for sampling algorithms for estimating the average
• Fast approximate probabilistically checkable proofs
• Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
• Sampling algorithms: lower bounds and applications
• On the Complexity of Sampling Vertices Uniformly from a Graph
• Non-interactive proofs of proximity
• A sample of samplers: a computational perspective on sampling
• scientific article; zbMATH DE number 7650126 (Why is no real title available?)
• Predicting winner and estimating margin of victory in elections using sampling
• Fully-Simulatable Oblivious Set Transfer
• Randomness in interactive proofs
• Testing graph blow-up
• Lower Bound for the Average Sample Size and the Efficiency of Ranking Sequential Procedures

This page was built for publication: Lower bounds for sampling algorithms for estimating the average

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