Lower bounds for sampling algorithms for estimating the average

DOI10.1016/0020-0190(94)00171-TzbMATH Open0875.68529MaRDI QIDQ674290FDOQ674290

Oded Goldreich, Guy Even, Ran Canetti

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)

Cites Work

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

Cited In (20)

• Randomness in interactive proofs
• Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs
• Lower Bound for the Average Sample Size and the Efficiency of Ranking Sequential Procedures
• Lower bounds for sampling algorithms for estimating the average
• Sampling algorithms for estimating the mean of bounded random variables
• Non-interactive proofs of proximity
• Fast approximate probabilistically checkable proofs
• Testing Graph Blow-Up
• Fully-Simulatable Oblivious Set Transfer
• Algorithmic Aspects of Property Testing in the Dense Graphs Model
• Learning distributions by their density levels: A paradigm for learning without a teacher
• On the Complexity of Sampling Vertices Uniformly from a Graph
• Metric-distortion bounds under limited information
• The query complexity of estimating weighted averages
• Introduction to Testing Graph Properties
• Introduction to Testing Graph Properties
• Predicting winner and estimating margin of victory in elections using sampling
• Testing Graph Blow-Up
• Title not available (Why is that?)
• A Sample of Samplers: A Computational Perspective on Sampling

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)