Randomness & Analysis of Algorithms

Team leaders: Verónica Becher (AR) and Loïck Lhote (FR)

The team is part of French-Argentinean International Research Project SINFIN (Université Paris 7-CNRS/Universidad de Buenos Aires-CONICET) which was created in 2019 as a continuation of the L.I.A. INFINIS (2011-2019).


General descriptionInstitutions involvedMembersProjects


Description: The team has two main research lines, one on randomness properties of finite and infinite sequences, the other centers on the probabilistic analysis of algorithms. The objects we study include trees, sequences and words, as well as finite state automata. Our research yields, not just average case complexity of algorithms and parameters of our data structures, but also the probability distribution. The work we carry out on sequences is relevant to the construction of communication codes, Montecarlo algorithms for numerical integration and pseudorandom number generators.

Philippe Flajolet
Computer scientist and mathematician. Member of the Academy of Sciences, left us , on March 22, 2011.

All of us, who work in the fields of mathematical informatics,
in France and abroad, we will not forget him. Philippe’s work accompanies us every day in our research and shows us the way.

Several members of this team worked hand by hand with Philippe Flajolet. (To know more about Philippe, click here)


The institutions involved are:

Projects

Stic-AmSud (EPAA) Entropy and Probabilistic Analysis in Algorithms. Coordinators: Eda Cesaratto (Ar), Paulina Cecchi (Cl), Pablo Rotondo (Fr) and Eduardo Canale (Uy), 2024-2025.

Stic-AmSud (RAPA2) Randomness and Probabilistic Analysis of Algorithms. Coordinators: Verónica Becher (Ar), Loïck Lhote (Fr) and Alfredo Viola (Ur), 2020-2021.

O. CARTON, Délégation CNRS spent at Universidad de Buenos Aires, julio 2018- julio 2019.

Stic-AmSud ALEA EN AMSUD. Coordinators: Eda Cesaratto (UNGS), Julien Clément (U. de Caen, Fr.) and Alfredo Viola (Univ. de la República, Ur), 2016-2017

ECOS PA17C04, “Randomness and finite-state machines”. Directores: V. Becher (Universidad de Buenos Aires) and O. Carton (Université de Paris Cité) 2018-2021

Stic-AmSud (DYNALCO) Advances in Analytic Combinatorics:dynamical combinatorics, and applications to number theory, information theory and cryptography. Coordinators: Eda Cesaratto (Ar), Brigitte Vallée (Fr) and Alfredo Viola (Ur), 2013-2014

FRICO8/01, Binational project Argentina-France, MINCyT-INRIA/CNRS, Laboratoire d’Informatique Algorithmique: Fondements et Applications (LIAFA) CNRS- Université Paris 7, Denis Diderot, “Aléatorieté etcombinatoire des mots”, 2009-2011.

V. Becher, Chercheur Étranger de la Mairie de Paris en qualité de senior CNRS et Université Paris Diderot – Laboratoire d’Informatique Algorithmique: Fondements et Applications (LIAFA) et Équipe de Logique Mathématique, November 2008 to February 2009.

FRIC06, Binational project Argentina-France , “Infinite sequences and algorithmic randomness “, SECyT-INRIA/CNRS, 2006-2008.