|
Abstract : |
We develop a framework to study probabilistic sampling algorithms that approximate general functions of the form f: A n! B, where A and B are arbitrary sets. Our goal is to obtain lower bounds on the query complexity of functions, namely the number of input variables x i that any sampling algorithm needs to query to approximate f(x 1; : : : ; xn). We dene two quantitative properties of functions | the block sensitivity and the minimum Hellinger distance | that give us techniques to prove lower bounds on the query complexity. These techniques are quite general, easy to use, yet powerful enough to yield tight results. Our applications include the mean and higher statistical moments, the median and other selection functions, and the frequency moments, where we obtain lower bounds that are close to the corresponding upper bounds. We also point out some connections between sampling and streaming algorithms and lossy compression schemes., |
