Polynomial Query Complexity and Algorithmic Learning I


The aim of the project is to develop and analyze the complexity of deterministic and
probabilistic learning algorithms -- mainly in the context of Angluin's model of
``exact learning via queries''. An important open question is whether Boolean circuits
are efficiently learnable. A promising approach to solve this question is to
systematically investigate the conditions under which a learning algorithm with
polynomially bounded query complexity can be converted into a polynomial time
algorithm.

Further goals of the project are to combine algorithmic and probabilistic approaches
and to apply techniques originally developed in learning theory to attack open problems
in complexity theory. Also, it is important to analyze the average-case complexity of
learning algorithms since in some cases, a worst case analysis might be to pessimistic
compared to the actual performance in practical applications.

The aim of the project is to develop and analyze the complexity of deterministic and
probabilistic learning algorithms -- mainly in the context of Angluin's model of
``exact learning via queries''. An important open question is whether Boolean circuits
are efficiently learnable. A promising approach to solve this question is to
systematically investigate the conditions under which a learning algorithm with
polynomially bounded query complexity can be converted into a polynomial time
algorithm.

Further goals of the project are to combine algorithmic and probabilistic approaches
and to apply techniques originally developed in learning theory to attack open problems
in complexity theory. Also, it is important to analyze the average-case complexity of
learning algorithms since in some cases, a worst case analysis might be to pessimistic
compared to the actual performance in practical applications.

Principal investigators
Köbler, Johannes Prof. Dr. (Details) (Algorithms and Complexity II)

Duration of project
Start date: 12/1999
End date: 10/2001

Research Areas
Algorithmisches Lernen, Komplexitätstheorie, Kryptographie

Last updated on 2022-08-09 at 03:05