ALEA Network

ALEA-NETWORK is an INTERNATIONAL SCIENTIFIC COORDINATION NETWORK (GDRI) created for a period of 4 years, starting on January 1, 2015.

The parties involved in this GDRI are the following:

• CNRS
• SORBONNE UNIVERSITE and LIP6
• UNIVERSITE PARIS 13 and LIPN- BORDEAUX INP
• UNIVERSITE PARIS DIDEROT and IRIF (former entitled LIAFA)
• UNIVERSITE VERSAILLES ST-QUENTIN EN YVELINES and LMV
• UNIVERSITÉ DE BORDEAUX as well as BORDEAUX INP and LABRI

• TECHNISCHE UNIVERSITÄT WIEN
• THE UNIVERSITY OF OXFORD
• LUDWIG-MAXIMILIANS-UNIVERSITÄT, LMU MÜNCHEN

Extended partners

• UPC (Barcelona)
• ACADEMIA SINICA (Taipei, Taïwan)
• STELLENBOSCH (South-Africa)
• TANANARIVE(Madagascar)

The common research objectives of the teams involved in ALEA-Network is the detailed analysis of properties of discrete random structures, coming from Computer Science, and other disciplines such as Probability, Theoretical Physics, and bio-informatics. Discrete models appearing in these disciplines are often strikingly similar and thus allow a common approach. For example, the study of percolation in theoretical physics is directly related to the theory of sandpiles in combinatorial theory; decryption of DNA in biology critically depends on text algorithms.

The main objects from Computer Science studied by the members of ALEA-Network come from analysis of algorithms and data structures. This includes trees, graphs and maps, random permutations, words, random sequences, random geometric objects, random Boolean formulae… These objects are naturally involved in algorithmic problems such as satisfiability problems, randomized algorithms, communication networks, and computer arithmetic. Members of ALEA-Network attempt at describing the structure of these objects, and expressing statistics, when the size of objects tends to infinity, under various probabilistic models.

The methods used, various and often complementary, are largely of mathematical nature: exact enumeration, asymptotic analysis, probabilistic properties, study of dynamical systems related to algorithms, methods from statistical physics.

The domains of application are multiples. The goal is to exploit the properties of the structures in order to evaluate and optimize algorithms in a variety of fields, such as:

• performance evaluation of basic data structures in Computer Science (words, trees, graphs), according to discrete or continuous probabilistic models;
• performance evaluation of algorithms in various fields such as arithmetic and semi-numeric algorithms , algorithms for symbolic manipulation and computer algebra, distributed and concurrent algorithms, communication protocols;
• study of randomized algorithms, particularly in the context of computational geometry, distributed algorithmic, or combinatorial optimization;
• algorithms for combinatorial optimization, Boolean formulas and random graphs, threshold phenomena;
• random generation and acceleration of simulation methods in the field of discrete structures;
• particle processes, which are interesting models both in physics, probability and combinatorics.

Probability theory allows for alternative approaches to some problems; in particular the opportunity to directly work on random functions (processes) allows to comprehensively describe some combinatorial objects (such as trees or planar maps, some cellular automata) and to obtain global qualitative results. Furthermore, probabilistic approaches are at the origin of efficient algorithmic approaches, e.g. for optimization problems (local search) and random generation (coupling from the past). Finally, the combinatorial approaches also provide new probability theorems, including results of continuous nature (discrete approach of Brownian, of continuous trees introduced by Aldous etc.).

Bioinformatics is an area where text algorithmic is crucial: design and analysis of algorithms for fast pattern matching, is absolutely essential for decrypting genomes. Other applications include processes of representations of large molecules, their folding simulation in models from thermodynamics and design of methods and objects for quickly classifying molecules, species, etc.

Statistical physics provides both new important and difficult combinatorial problems (e.g. related to Ising and Potts models or planar maps) and new methodologies (e.g. matrix integrals).