Polynomial Query Complexity and Algorithmic Learning II


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)

Financer
DFG: Sachbeihilfe

Duration of project
Start date: 11/2001
End date: 12/2003

Last updated on 2022-08-09 at 01:07