All reports by Author Efim Kinber:

__
TR95-036
| 5th July 1995
__

Richard Beigel, William Gasarch, Efim Kinber#### Frequency Computation and Bounded Queries

Richard Beigel, William Gasarch, Efim Kinber

For a set A and a number n let F_n^A(x_1,...,x_n) =

A(x_1)\cdots A(x_n). We study how hard it is to approximate this

function in terms of the number of queries required. For a general

set A we have exact bounds that depend on functions from coding

theory. These are applied ...
more >>>