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 >>>

Till Tantau

A language is \emph{selective} if there exists a

selection algorithm for it. Such an algorithm selects

from any two words one, which is an element of the

language whenever at least one of them is.

Restricting the complexity of selection algorithms

yields different \emph{selectivity classes} ...
more >>>