Jan Arpe, RĂ¼diger Reischuk

Detecting the relevant attributes of an unknown target concept

is an important and well studied problem in algorithmic learning.

Simple greedy strategies have been proposed that seem to perform reasonably

well in practice if a sufficiently large random subset of examples of the target

concept is provided.

Introducing a ... more >>>

Nader Bshouty

Consider the model where we can access a parity function through random uniform labeled examples in the presence of random classification noise. In this paper, we show that approximating the number of relevant variables in the parity function is as hard as properly learning parities.

More specifically, let $\gamma:{\mathbb R}^+\to ... more >>>