[FOM] Caleidoscope: Research School in Computational Complexity, Paris (France), 17-21 Jun 2019

Anupam Das anupamdotdas at gmail.com
Thu Mar 28 12:49:44 EDT 2019

*** Call for participation***

Caleidoscope: Research School in Computational Complexity
Institut Henri Poincaré, Paris, 17-21 June 2019

Dear all,

This is the second announcement for the Caleidoscope Research School in 
Computational Complexity, to take place at the Institut Henri Poincaré, 
Paris 17-21 June 2019. The school is aimed at graduate students and 
researchers who already work in some aspects of computational complexity 
and/or who would like to learn about the various approaches.

*Important news:*

-  the registration deadline is set to *19 May 2019*;
-  we are now accepting applications for *financial support*for 
participants (see below for the details).


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.

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 
neighbouring areas.


1. Boolean circuits and lower bounds. (Rahul Santhanam, University of 
2. Algebraic circuits and geometric complexity. (Peter Bürgisser, 
Technical University Berlin)
3. Proof complexity and bounded arithmetic. (Sam Buss, University of 
California San Diego)
4. Machine-free complexity (descriptive and implicit complexity). (Anuj 
Dawar, University of Cambridge and Ugo Dal Lago, University of Bologna)

In addition to these broad-ranging themes, there will also be three more 
focussed topics, providing examples of (already established or 
potential) interactions between logic, algebra and complexity:

5. Constraint satisfaction problems. (Libor Barto, Charles University in 
6. Communication complexity. (Sophie Laplante, Paris 7 University)
7. Duality in formal languages and logic. (Daniela Petrisan, Paris 7 


Registration to the school is free but mandatory. This is to help us 
plan tea/coffee breaks and social activities.


The deadline for registration is *19 May 2019*.


Financial support is available for participants.  You may apply by 
filling in the following online form:


Please send your application no later than *14 April 2019* to maximize 
your chances of being considered.  (Our funds being limited, we 
apologize in advance if your support request will only be met partially 
or declined).

Also note that *student*members of the ASL (Association for Symbolic 
Logic) may apply for travel support (not lodging!) by contacting 
directly ASL and mentioning attendance to Caleidoscope (which is 
sponsored by ASL).


Funding sponsors:
DIM RFSI - Région Île-de-France (https://dim-rfsi.fr/)
Agence Nationale de la Recherche 
CNRS (http://www.cnrs.fr/en)
SIGLOG (https://siglog.hosting.acm.org/)
The European Commission (https://ec.europa.eu/commission/index_en)
Université Paris 13 (https://www.univ-paris13.fr/)
Laboratoire d'Informatique de Paris Nord (https://lipn.univ-paris13.fr/)
Association for Symbolic Logic (http://aslonline.org/)

Other sponsors:
European Association for Computer Science Logic (http://www.eacsl.org/)
Société Mathématique de France (https://smf.emath.fr/)

More information about the FOM mailing list