June 17-21, 2019
Research school in computational complexity. 17-21 June 2019, Institut Henri Poincaré, Paris.
The Caleidoscope school will be comprise of four main lecture courses, based on some of the most developed approaches to computational complexity today.
1. Boolean circuits and lower bounds. (Rahul Santhanam, University of Oxford).
2. Algebraic circuits and geometric complexity. (Peter Bürgisser, Technical University Berlin).
3. Proof complexity and bounded arithmetic; (Samuel 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 Prague). 6. Communication complexity. (Sophie Laplante, Paris 7 University).
7. Duality in formal languages and logic. (Daniela Petrisan, Paris 7 University).