Lower bounds for sampling algorithms for estimating the average

DOI10.1016/0020-0190(94)00171-TzbMath0875.68529MaRDI QIDQ674290

Oded Goldreich, Guy Even, Ran Canetti

Publication date: 28 February 1997

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

zbMATH Keywords

EstimatingLower boundsSamplingRandomnessTheory of computation

Mathematics Subject Classification ID

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

Related Items

Fast approximate probabilistically checkable proofs, Learning distributions by their density levels: A paradigm for learning without a teacher, Metric-distortion bounds under limited information, Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs, Fully-Simulatable Oblivious Set Transfer, Unnamed Item, Algorithmic Aspects of Property Testing in the Dense Graphs Model, Introduction to Testing Graph Properties, On the Complexity of Sampling Vertices Uniformly from a Graph, Lower bounds for sampling algorithms for estimating the average, Predicting winner and estimating margin of victory in elections using sampling, Non-interactive proofs of proximity, Testing Graph Blow-Up, Testing Graph Blow-Up, A Sample of Samplers: A Computational Perspective on Sampling, Introduction to Testing Graph Properties, The query complexity of estimating weighted averages, Randomness in interactive proofs

Cites Work

• Unnamed Item
• Lower bounds for sampling algorithms for estimating the average
• Monte-Carlo algorithms for the planar multiterminal network reliability problem
• Private vs. common random bits in communication complexity
• Tiny families of functions with random properties (preliminary version)
• Monte-Carlo approximation algorithms for enumeration problems
• Probability Inequalities for Sums of Bounded Random Variables