# 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.

### News

Laurent Bienvenu visits Poncelet lab for the Complexity Year. He will teach a course (+seminar) on Kolmogorov Complexity and Computability. He will introduce this course at his talk at Kolmogorov Seminar (16 Sep., 16:45-18:30, 16-04, Main Building of Moscow State University). The talk and the course will be in English, and prospective participants are cordially invited. The course will probably start after the CCR 2013 (ccr2013.mccme.ru, 23--28 September) conference, where L.B. is one of the invited speakers, and the people interested in Kolmogorov complexity are invited, too.В рамках года сложности в лабораторию Понселе на целый год приезжает Laurent Bienvenu (Париж, LIAFA), который организует спецкурс-спецсеминар Kolmogorov Complexity and Computability (при участии Н.Верещагина, А.Ромащенко и А.Шеня).

Потенциальные участники приглашаются на его доклад на колмогоровском семинаре 16 сентября в 16:45 в аудитории 16-04 ГЗ МГУ, где он расскажет про свои работы и обсудит программу будущего курса. Язык доклада и курса - английский.

Предположительно занятия будут происходить в НМУ и начнутся после конференции CCR2013 (23-28 сентября), посвящённой колмогоровской сложности. Заседания конференции будут в МЦНМО; Laurent Bienvenu - один из докладчиков (см. расписание), и потенциальные участники приглашаются на его доклад (и другие)

**20 August. 11:00–14:00. Mark Braverman (Princeton).**

Information complexity and precise bounds for communication complexity. (in Russian)