Invited Speakers 
SPEAKING IN ENGLISH
John Kearns (Buffalo University)
Damian Niwiński (University of Warsaw)
http://www.mimuw.edu.pl/~niwinski/
In search of the shortest description
``This one [letter] would not be so long had I but the leisure to make it shorter.''
This phrase of Blaise Pascal from his Lettres provinciales (1657) brings to our attention a precious value of shortness. But is this always possible ?
For example, can we make a sequence
100102012201120100021102201201201102211012
much shorter ?
In a so-called 20 question game, a thinker invents an object X (presumably, from some large set S), and the remaining players try to identify it by asking questions (normally, up to 20), the answers to which can be only yes or no. Knowing thinker's preferences may help. More precisely, an optimal strategy exists, assuming we know the probability of each object to be invented. The series of questions leading to a given object according to the optimal strategy can be viewed as a shortest description of the object. This gives rise to a complexity measure in the information theory due to Claude Shannon (1916-2001).
An alternative concept, proposed by Andrey Kolmogorov (1903-1987) measures the complexity of an object by the length of a shortest program needed to generate it. Surprisingly, these two concepts meet in a beautiful theorem (emerging from the work of several mathematicians). If the probability of an object is understood as the probability of its generation by a randomly chosen program, then the two measures turn out to (reasonably) coincide.
The purpose of the lecture is to understand better the meaning of this theorem.
SPEAKING IN POLISH
Andrzej Chmielecki (University of Gdańsk)
http://www.ifsid.ug.gda.pl/filozofia/pracownicy/a_chmielecki/