Complexity Year

Poncelet French-Russian Laboratory,

Moscow, Russia

2013 ? 2014

Organisers

Thomas Fernique (LIPN, Paris Nord)

Andrei Romashchenko (Laboratoire J.-V. Poncelet Moscow ? LIRMM Montpellier)

Alexander Shen (LIRMM Montpellier)

Nikolay Vereshchagin (Laboratoire J.-V. Poncelet Moscow ? MSU Moscow)

Laurent Bienvenu (Laboratoire J.-V. Poncelet Moscow ? LIAFA, Paris)

General Information

One of most important discoveries of the XXth century (and, may be, in the entire history of mankind up to now) was the introduction of the notion of algorithm. Examples of algorithms were known for centuries, but the general notion of an algorithm was needed to show that there are algorithmically unsolvable (undecidable) problems. They are closely related to classical results of mathematical logic, such as G\"odel incompleteness theorem; they attracted a lot of attention from philosophers and other general public. This happened in 1930s; in 1960s and 1970s it became clear that the philosophically important dividing line goes not only between decidable and undecidable problems, but also between ``feasible'' and ``unfeasible'' problems. It turned out that there are some problems that are decidable in the sense of general computation theory, but from any practical purpose they can be treated as undecidable ones: the deciding algorithms require enormous time and use enormous space for the computation.

The complexity theory studies the resources needed for some algorithmic tasks: the length of a program needed to produce some object (Kolmogorov complexity, or algorithmic information theory), the time and space needed to perform some computation task (computational complexity theory), the number of elements in a circuit that performs some information processing (circuit complexity theory). The central problem of this field (the famous P=NP question, the construction of one-way function needed for public-key cryptography, lower bounds for circuit complexity) are still open, but nevertheless the complexity theory proved to be a rich and mathematically interesting theory where philosophical motivations (e.g., the notion of an interactive proof or zero-knowledge proof) are closely related with new fundamental results (like NP-completeness of approximation problems).

The Complexity year will extend the existing cooperation between the researchers from Moscow State University (Kolmogorov complexity seminar, Math Dept), Moscow Physics Technical University, Steklov institute, and researchers from LIAFA, LIRMM and other laboratories in France. Two workshops, Franco-Russian workshop on Algorithms, complexity and applications and an Annual conference on Computability, Complexity and Randomness will happen in June and Sept. 2013, respectively. There will be a weekly course/seminar run by L.Bienvenu, N.Vereshchagin and others devoted to Kolmogorov complexity and computability theory, as well as some other topics.