17-21 Jun 2019 Paris (France)

Description

Computational complexity theory was born more than 50 years ago when researchers started asking themselves what could be computed efficiently. Classifying problems/functions with respect to the amount of resources (e.g. time and/or space) needed to solve/compute them turned out to be an extremely difficult question.  This has led researchers to develop a remarkable variety of approaches, employing different mathematical methods and theories.

We believe that the future development of complexity theory will require a subtle understanding of the similarities, differences and limitations of the many current approaches. In fact, even though these study the same phenomenon, they are developed today within disjoint communities, with little or no communication between them (algorithms, logic, programming theory, algebra...). This dispersion is unfortunate since it hinders the development of hybrid methods and more generally the advancement of computational complexity as a whole.

The goal (and peculiarity) of the Caleidoscope school is to reunite in a single event as many different takes on computational complexity as can reasonably be fit in one week.  It is intended for graduate students as well as established researchers who wish to learn more about neighboring areas.

Lectures

Among the many approaches to complexity, we selected those for which there are already some results establishing connections, or for which such connections seem to us particularly accessible:

1. Boolean circuits and lower bounds;
2. Algebraic circuits and geometric complexity;
3. Proof complexity and bounded arithmetic;
4. Machine-free complexity (descriptive and implicit complexity).

In addition to these broad-ranging themes, we also chose three more specific topics, providing examples of (already established or potential) interaction between logic, algebra and complexity:

5. Constraint satisfaction problems;
6. Communication complexity;
7. Duality in formal languages and logic.

Organizers

Anupam Das (DIKU, Copenhagen)

Damiano Mazza (CNRS, LIPN, Université Paris 13)

Thomas Seiller (CNRS, LIPN, Université Paris 13)

Online user: 1