Polynomial Query Complexity and Algorithmic Learning
DFG Research Project
Project supported by Deutsche Forschungsgemeinschaft (DFG), Germany.
Duration: November 1999 to October 2003.
Project Members
| Institution | Project Member |
| Humboldt University, Berlin, Germany. | Johannes Köbler |
| Wolfgang Lindner |
Research background
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.