12-16 Jun 2023 Ile d'Oléron (Oleron Island) (France)

Description

Computational complexity theory was born nearly 60 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 EPIT 2023 (École de printemps d'informatique théorique), which marked the 50th edition of this series of research schools, reunited in a single event as many different takes on computational complexity as can reasonably be fit in one week.  It was intended for Ph.D. students as well as established researchers who wish to learn more about neighboring areas.

Topics

The school consisted of 6 courses, on the following topics:

  1. Descriptive Complexity (Albert Atserias, Universitat Politècnica de Catalunya)
  2. Randomness (Valentine Kabanets, Simon Fraser University)
  3. Lower Bounds (Paul Beame, University of Washington)
  4. Hardness of Approximation (Irit Dinur, Weizmann Institute)
  5. Parameterized Algorithms and Fine-Grained Complexity (Michał Pilipczuk, University of Warsaw)
  6. Algebraic and Geometric Complexity (Guillaume Malod, IMJ, and Christian Ikenmeyer, University of Warwick)

The typical course comprised three 90-minute lectures, and the program included time for discussions.

 

Anti-Harassment Policy

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 followed the anti-harassment policy of ACM.

 

Organizers

  • Damiano Mazza (CNRS, LIPN, Université Sorbonne Paris Nord)
  • Joanna Ochremiak (CNRS, LaBRI, Université de Bordeaux & University of Warsaw)
  • Sylvain Perifel (IRIF, Université Paris Cité)
  • Thomas Seiller (CNRS, LIPN, Université Sorbonne Paris Nord)

 

Contact

For any questions about the school, please send an email to epit2023@sciencesconf.org.

Online user: 2 Privacy
Loading...