I & M
Home > Spotlight > Project Team > I & M

I & M

Fundamental Computing & Discrete Mathematics

Context

During the last decades, a very strong interaction between mathematics and computer science has developed. Thus, classical topics such as geometry, topology, algebra, probabilities or classical and non-classical logics are used to describe and understand discrete structures arising from computer science problems. Reciprocally, tools from computer science allow to better understand certain mathematical properties. The main objectives can be summarized as follows: to give discrete representations of continuous objects, to develop mathematical tools to study discrete structures, to explore mathematical properties through computation, to optimize and give limits to the complexity of the algorithms used, to develop a theory of computer-assisted proof.

From the national point of view, these themes are the main axes of the gdr-im which gathers about 1500 permanent members. These themes are found scattered in the different teams of the IRIT, LAAS and IMT laboratories. In recent years, the Labex CIMI has developed some activities in these directions (CIMI meetings, funding of mini projects, postdoc ...).

The creation of a project team allows to create a dynamic around discrete mathematics and fundamental computer science.

Project

The interaction of fundamental computer science and the development of discrete mathematical tools

to model these problems is very rich, we can underline the following tracks:

  • Discrete models and systems: A computer manipulates discrete objects, it is natural to be interested in such objects, to understand their combinatorics, their structural complexity and try to describe the properties of a generic element. One can also ask oneself how to encode continuous objects by discrete objects to manipulate them computationally.

  • Algorithms on these structures: It is interesting to develop efficient algorithms to solve problems on these structures. We can therefore be interested in the complexity of these algorithms, understand if there are instances that are more difficult than others and if this is the case study the phase transitions that can appear. The study of these algorithms requires, among other things, the use of the logic formalism.

  • Proof: The combinatorial explosion of the study of certain discrete objects makes it interesting to develop efficient proof assistants. This problem is related to logic, certification of algorithms and proofs of programs.

  • Transversal themes: There may be themes that are transversal to this division on the themes of mathematical security (coding, cryptography, software verification).