Prof. Dr. Tobias Friedrich


Paper accepted at STACS 2016

The 33rd International Symposium on Theoretical Aspects of Computer Science (STACS 2016) is a leading conference which topics range from the theory of algorithms to the application of mathematical logic in computer science. We are pleased to announce that the following paper of our research group has been accepted:

Towards an Atlas of Computational Learning Theory

Timo Kötzing and Martin Schirneck

Abstract: A major part of our knowledge about Computational Learning stems from comparisons of the
learning power of different learning criteria. These comparisons inform about trade-offs between
learning restrictions and, more generally, learning settings; furthermore, they inform about what
restrictions can be observed without losing learning power. With this paper we propose that one main focus of future research in Computational Learning should be on a structured approach to determine the relations of different learning criteria. In particular, we propose that, for small sets of learning criteria, all pairwise relations should be determined; these relations can then be easily depicted as a map, a diagram detailing the relations. Once we have maps for many relevant sets of learning criteria, the collection of these maps is an Atlas of Computational Learning Theory, informing at a glance about the landscape of computational learning just as a geographical atlas informs about the earth. In this paper we work toward this goal by providing three example maps, one pertaining to partially set-driven learning, and two pertaining to strongly monotone learning. These maps can serve as blueprints for future maps of similar base structure.