Complexity is one of the core areas of ICALP and it plays an important role in many investigations undertaken in learning theory. There is a rich variety of investigations in learning theory that involve in one way or another complexity theoretic studies. These studies comprise the design and analysis of learning algorithms from the perspective of complexity. On the one hand, the computational complexity is studied, where different complexity measures are considered. On the other hand, the main focus may be the informational complexity. Such studies often reveal close relationships to active research areas in complexity theory, e.g., the design of efficient approximation algorithms, inventing new data structures, or solving combinatorial optimization problems.

Furthermore, Kolmogorov complexity plays an important role in various branches of learning theory and in the last decades we have seen an enormous progress in all related areas. Of course, here a major new problem arises, since the Kolmogorov complexity is not computable.

Last but not least, complexity theoretical investigations also have two sides. Often, we are interested in finding the most efficient solution to a learning problem. However, several aspects of learning theory which may be roughly summarized by maintaining at least a certain aspect of privacy, are based on the opposite side. That is, when dealing with such problems, the privacy protection is often based on the computational hardness (proved or conjectured) of several problems. Thus, there are also close connections to cryptography (and former workshops held at ICALP meetings).

Thus, it is hoped that this workshop may help to stimulate intensive interaction between the complexity theory community and the learning theory community.

To summarize, we invite submissions of all areas of learning theory (including teachability) and complexity that shed new light on our understanding of the potentials and limitations of learning theory.

Submissions will be judged with respect to clarity, significance and originality. The best papers will be invited to be published as postproceedings.

Last update February 7, 2013