Research school in computational complexity. 15-19 June 2020, Paris.

Caleidoscope is CANCELLED

We are sorry to announce that, due to the ongoing COVID-19 epidemic, the 2020 edition of the Caleidoscope school is CANCELLED.  We hope we will be able to propose these great lectures in the summer of 2021.


Computational complexity theory was born more than 50 years ago when researchers started asking themselves what could be computed efficiently. Classifying problems or functions with respect to the amount of resources (e.g. time and/or space) needed to solve or 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.

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 approaches study the same phenomenon, they are developed today within disjoint communities, with little or no communication between them (e.g. algorithms, logic, programming theory, algebra etc.). 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.


The 2020 Caleidoscope school will be comprised of four main lecture courses, based on some of the most developed approaches to computational complexity today.

1. Algorithms and lower bounds. Lecturer: Ryan Williams, MIT.
2. Hardness of Approximation. Lecturer: Luca Trevisan, Bocconi University.
3. Higher-Order Complexity. Lecturer: Bruce Kapron, University of Victoria.
4. Parametrized Complexity. Lecturer: Daniel Marx, Max Planck Institute Saarbrucken.

In addition to these broad-ranging themes, there will also be three more focussed topics.

5. Quantum Verification and Complexity. Lecturer: Elham Kashefi, CNRS and Sorbonne University.
6. Static Complexity Analysis. Lecturer: Georg Moser, University of Innsbruck.
7. Complexity Theory for Black-Box Optimization Heuristics. Lecturer: Carola Doerr, CNRS and Sorbonne University.


We believe that the advancement of research is best accomplished in an environment that is open, diverse and respectful to all participants. During the school, we will follow the anti-harassment policy of ACM.


Previous Editions

Online user: 1