Welcome

The ELC Workshop on Learning Theory and Complexity will be held on September 16, 2014 in Kyoto University, Japan. The workshop is the second one, following the ICALP 2013 Satellite Workshop on Learning Theory and Complexity, which was held in University of Latvia last year. This year we added the prefix "ELC" to the workshop name, in order to explicitly indicate that the workshop is sponsored by "Exploring the Limits of Computation (ELC)", a five-year research project starting in 2012 in Japan.

The project ELC aims at finding the next steps toward a big breakthrough in complexity theory, by bringing together the knowledge and wisdom from various research fields related to computation in some way, such as logic, information theory, memory-constrained algorithms, optimization, mathematical programming, succinct data structures, statistical mechanics, quantum mechanics, and LEARNING.

The process of learning can be viewed as interactive computation against probabilistic or adversarial environments under the lack of information needed to identify solutions. For instance, online optimization is the problem of finding (predicting) a solution \(x\) in an attempt to minimize \(f(x)\) BEFORE seeing the objective function \(f\), whereas in the ordinary optimization \(f\) is given beforehand as input. So in-depth studies on various learning problems will provide different views and novel insights into deep understanding of computation, which will hopefully lead to useful analysis techniques for investigating the limits of computation.

We hope that this workshop may help to stimulate intensive interaction between the complexity theory community and the learning theory community.

The workshop is twofold, the invited talk session and the ELC session. In the first session, three distinguished researchers are invited to give talks about their late-breaking results, and in the second session, selected members from the ELC project exhibit their recent achievements and/or ongoing research projects with short talks + posters.

ICGI 2014, the 12th International Conference on Grammatical Inference will be held after this workshop, September 17-19, at the same conference room. It is expected that the participants of the workshop will also attend the main conference ICGI.

Workshop Chairs: Eiji Takimoto and Ryo Yoshinaka