Randomness-efficient oblivious sampling
- 17 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 276-287
- https://doi.org/10.1109/sfcs.1994.365687
Abstract
We introduce a natural notion of obliviousness of a sampling procedure, and construct a randomness-efficient oblivious sampler. Our sampler uses O(l+log /spl delta//sup -1//spl middot/log l) coins to output m=poly(/spl epsiv//sup -1/, log /spl delta//sup -1/, log l) sample points x/sub 1/, ..., x/sub m/, /spl isin/ {0, 1}/sup 1/ such that Pr[|1/m/spl Sigma//sub i=1//sup m/f(x/sub i/)-E[f]|Keywords
This publication has 19 references indexed in Scilit:
- A Chernoff bound for random walks on expander graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Tiny families of functions with random properties (preliminary version)Published by Association for Computing Machinery (ACM) ,1994
- Algebraic methods for interactive proof systemsJournal of the ACM, 1992
- On the power of two-point based samplingJournal of Complexity, 1989
- The Knowledge Complexity of Interactive Proof SystemsSIAM Journal on Computing, 1989
- Dispersers, deterministic amplification, and weak random sourcesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- How to recycle random bitsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1989
- Private coins versus public coins in interactive proof systemsPublished by Association for Computing Machinery (ACM) ,1986
- Universal classes of hash functionsJournal of Computer and System Sciences, 1979
- Probability Inequalities for Sums of Bounded Random VariablesJournal of the American Statistical Association, 1963