Algorithmic complexity was born nearly 60 years ago, when researchers began to question what it meant to compute efficiently.
Classifying problems or functions based on the amount of resources (time, space, etc.) required to solve or compute them has proven to be
an extremely challenging task. This has led researchers to develop a remarkable variety of approaches, employing diverse mathematical methods
and theories.
Although our laboratory does not have a team solely dedicated to this subject, algorithmic complexity is present at LIPN in various forms and across several teams:
- the links between logic and complexity form the basis of one of the main research areas of the LoVe team;
- analyzing the complexity of optimization problems, or their approximability, is a key aspect of the AOC team’s work;
- the study of average-case complexity, approached through combinatorial methods, is a focus within the CALIN team;
- the connections between algebraic complexity and certain combinatorial aspects of representation theory are of interest to both the LoVe and CALIN teams;
- finally, compelling complexity questions can potentially arise in more applied research, such as that conducted by the A3 and RCLN teams.
The objective of the “Complexities” cross-disciplinary axis is to federate and structure all the research mentioned above. Its activities include:
- organizing a regular seminar, where LIPN members interested in complexity can study a subject in depth, share their research, and potentially develop cross-team collaborations;
- organizing scientific events with external guests, such as thematic workshops.