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.
Albeit our laboratory does not host a research group solely focused on this topic, computational complexity does appear at LIPN under many different guises and in several different research groups:
- the connections between logic and complexity are one of the main research directions of the LoVe team;
- understanding the computational complexity of optimization problems, or their approximability, is an important aspect of the research developed in the AOC team;
- the average complexity analysis of algorithms, using combinatorial methods, is present in the CALIN team;
- connections between algebraic complexity and certain combinatorial aspects of representation theory are of interest to both the LoVe and CALIN teams;
- finally, more applied research, as the one carried in the A3 and RCLN teams, sometimes stumbles on interesting complexity questions.
The aim of this cross-lab research axis, deemed “Complexity”, is to federate and give structure to all of the above kinds of research. Its activities consist in:
- a regular seminar, where members of LIPN interested in complexity learn in-depth about selected topics, share their research and possibly develop inter-group collaborations ;
- organising scientific events (such as small workshops) open to everyone, in particular inviting researchers from outside LIPN.
Coordinators: Daminao Mazza and Thomas Seiller