Supervisory authorities



Home > What is IQFA ? > Involved laboratories > Rhône-Alpes > Laboratoire d’Informatique et du Parallèlisme (LIP)

Computational Modelling and Complexity

by Sebastien_Tanzilli - published on , updated on

Main contact: Pascal Koiran
Other contacts: Natacha Portier

Research activities:

We try to understand the power and limitations of efficient algorithms. Toward this end we design and analyze algorithms, and we set impossibility results (i.e., completeness results or whenever possible unconditional lower bounds).

Algorithms can be sequential, parallel, distributed, synchronous or asynchronous, deterministic, probabilistic or quantum. Efficiency is quantified through complexity measures like computation time or memory requirements or volume of data exchanged. Besides classical sequential machines and in order to focus the attention on one or several of these different aspects of computation, we may consider various models of computation such as, for example, boolean circuits, quantum machines or networks of automata.

Strong attention is given to the study of algorithms on discrete structures and algebraic algorithms.

Various fields of mathematics, in particular combinatorics, are at the heart of this research.

For more information: see online Models @ complexity @ LIP