Board and administration

Directeur : Pierre Fraigniaud

Secrétariat : Noëlle Delgado

Tél : +33(0)1 57 27 92 56 - Fax : +33(0)1 57 27 94 09

Adresse : Université Paris Diderot, Case 7014, Bâtiment Sophie Germain, 75205 Paris Cedex 13



The number of full-time members of LIAFA is sixty, including roughly 34 academics from university Paris Diderot, 24 CNRS researchers, and 2 INRIA researchers. The total number of LIAFA members, including PhD students, post-docs, administrative and technical staffs, and long-term visitors amounts to about 110 people.

Research at LIAFA is divided into five main areas :

- Algorithms and complexity (Group leader: Frédéric Magniez)
- Automata and applications (Group leader: Olivier Serre)
- Combinatorics (Group leader: Sylvie Corteel)
- Distributed algorithms and graphs (Group leader: Nicolas Schabanel)
- Modeling and verification (Group leader: Ahmed Bouajjani)

Research themes

- Algorithms and complexity

The theory of efficient algorithms is the common ground that brings together the research directions we investigate, in both classical computing and quantum computing. 

In the area of classical computing, we study the complexity of various problems in several models of computation, designing efficient algorithms and proving lower bounds. The particular fields we study are approximation algorithms, property testing, streaming algorithms, online algorithms, algorithmic game theory, communication complexity, and theoretical cryptography. Many of the problems to be studied in these fields require, or can benefit from, probabilistic approaches. 

In quantum computing our goals are to study the power of quantum algorithms, to enhance our understanding of the strength of quantum information for computational tasks, cryptography and interaction, and to explore the relation between classical and quantum communication complexity. 

The flow of ideas and techniques between quantum and randomized computing, in the two directions, is an important characteristic of some of the research within our group.

- Distributed algorithms and graphs: 

The research topics addressed by the team Distributed algorithms and graphs cover the following fields: graph algorithms and distributed computing. 

The team possesses a strong expertise in algorithmic for graph decomposition, and in the design and analysis of algorithms dedicated to graph families with specific properties such as hyperbolic metrics, doubling metrics, or fixed minor excluding. In addition, the team covers most of the topics in distributed computing, from the fault tolerant theory (consensus, leader election, failure detectors, etc.) to network computing (routing, compact labeling, coloring, spanners, etc.). 

The application domains of the team are mostly related to the design of protocols for peer-to-peer networks, and to the analysis of various types of social networks (Web graph, acquaintance network, small worlds, etc.). Part of the team members are actually also members of the INRIA project GANG whose objective is to develop algorithmic methods for the design and management of large networks.

- Automata and applications:

The research carried out at the Automata and applications team covers the fundamental aspects of automata theory, as well as algorithmic questions arising from concrete problems. The fundamental aspects concern mainly semigroups, combinatorics on words, the link with logic, topology, games, etc. In the recent years, special effort has been devoted to the extensions of the notion of automaton : automata on infinite or even transfinite words, automata with output, etc. Concerning applications, the team is working on problems arising from model checking, discrete event systems modelling, computer arithmetic, and on algorithms for the automatic recognition in genetic sequences. 

- Combinatorics

- Modeling and verification:

The research activities of the Modeling and Verification team address the development of algorithmic approaches to system verification, from theoretical foundations to innovative verification tools. 

The applications are in a wide spectrum including distributed algorithms, dynamic networks of communicating processes, real-time systems, safety critical embedded systems, programs with complex data structures, concurrent programs, etc. 

The adopted approaches are in general based on the use of (1) formal models describing the behaviors of the systems at some abstraction level, (2) formal specifications describing the properties that these systems should satisfy, and (3) algorithmic methods for either establishing the correctness, or detecting illegal behaviors, of a system with respect to its specification. 

The models and specification formalisms are in general either automata-based (finite-state automata, pushdown automata, timed or counter automata, etc.) or logic-based (temporal logics, monadic first/second order logics, fixpoint calculi, etc.), and verification problems are often reduced to decision problems for these formalisms such as reachability/language emptiness for the automata, satisfiability/validity for the logics, winning strategies for games, etc. The main issues concern the decidability and the complexity of these problems, as well as the development of efficient verification techniques based on (upper/lower) refinable approximate analysis. 

The team has competences in infinite-state verification, verification/synthesis of timed and hybrids systems, temporal logics, games and model-checking, quantitative model-checking, program verification.

Laboratoire d’Informatique Algorithmique : Fondements et Applications

UMR 7089 Université Paris Diderot