| 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