ALGORITHMS Research team

Algorithms

Team presentation

Algorithms: Analysis of complex discrete systems with random behaviours; tools for automated analysis in computer algebra. Tools for the quantitative study of probabilistic algorithms.
Computer algebra: complex functional systems, fast algorithms, differential systems, special functions.

Research themes

Scientific areas:
Algorithm analysis and optimization require an indepth understanding of random discrete structures such as words, trees, graphs, permutations etc. Indeed, the efficiency of most commonly used algorithms depends on the expected pattern of the processed data. ALGORITHMS gives precise results for the typical behaviour of algorithms, aiming at realistic data models. It develops methods based on links between combinatorial properties and the behaviour of analytic functions. Given the very systematic nature of its approach, ALGORITHMS also aims to develop decision methods which can be implemented in computer algebra. This approach is a powerful driver of change and has led to the revision of conventional approaches in computer algebra; in this domain, research to a large extent revolves around the study of special functions and series expansions. The goal is to provide a reliable and comprehensive algorithmic toolbox for large classes of problems arising from combinatorics or conventional analysis.

Milestone:
Developed by ALGORITHMS, Hyperloglog is the best algorithm known for cardinality estimation of very large data sets. In a data set which may contain billions of objects, it uses very little memory to assess the number of different objects. Complexity records in several areas of basic computer algebra algorithms and in the processing of large differential systems have been obtained.

Software:
Algolib: Maple library for analyzing combinatorial structures, generating functions, differential or linear recurrent equations, linear operator systems.

International and industrial relations

  • Universities of Princeton, Linz, Pierre & Marie Curie, Caen and École Polytechnique.
  • GDR Informatique mathématique (research working groups in computer science & mathematics) - Alea and Computer algebra working groups.
  • ANR Gecko (French National Research Agency's geometric approach to complexity) and SADA (random discrete structures and algorithms) projects.
  • Master Parisien de Recherche en Informatique; École Polytechnique.

Keywords: Analysis of algorithms Computer algebra

Research teams of the same theme :

Inria Headquarters and research centres

Direct links

Social