All reports by Author Jan Arpe:

__
TR06-065
| 24th May 2006
__

Jan Arpe, RĂ¼diger Reischuk#### When Does Greedy Learning of Relevant Features Succeed? --- A Fourier-based Characterization ---

__
TR06-045
| 13th March 2006
__

Jan Arpe, Bodo Manthey#### Approximability of Minimum AND-Circuits

Revisions: 1

__
TR05-088
| 3rd August 2005
__

Jan Arpe#### Learning Juntas in the Presence of Noise

__
TR03-083
| 21st November 2003
__

Jan Arpe, Andreas Jakoby, Maciej Liskiewicz#### One-Way Communication Complexity of Symmetric Boolean Functions

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

Jan Arpe, Bodo Manthey

Given a set of monomials, the Minimum AND-Circuit problem asks for a

circuit that computes these monomials using AND-gates of fan-in two and

being of minimum size. We prove that the problem is not polynomial time

approximable within a factor of less than 1.0051 unless P = NP, even if

more >>>

Jan Arpe

The combination of two major challenges in machine learning is investigated: dealing with large amounts of irrelevant information and learning from noisy data. It is shown that large classes of Boolean concepts that depend on a small number of variables---so-called juntas---can be learned efficiently from random examples corrupted by random ... more >>>

Jan Arpe, Andreas Jakoby, Maciej Liskiewicz

We study deterministic one-way communication complexity

of functions with Hankel communication matrices.

Some structural properties of such matrices are established

and applied to the one-way two-party communication complexity

of symmetric Boolean functions.

It is shown that the number of required communication bits

does not depend on ...
more >>>