AmSud: Entropy and Probabilistic Analysis in Algorithms

This is a STIC-AmSud project.

Description – Members of EPAA – Meetings

News and Meetings

Virtual meeting: May 29-30, 2024. Webpage here
Kick-off meeting: Buenos Aires (Argentina), October 21-25, 2024. Webpage here

Description

Coordinators: Eda Cesaratto (Ar), Paulina Cecchi (Ch), Pablo Rotondo (Fr), Eduardo Canale (Ur)

Acronym: EPAA
Period: 2024-2025

The project lies at the interface between Computer Science and Mathematics, in various fields, linked together by the notion of entropy, as a measure of complexity, as well as the presence of randomness. Our objects of study are algorithms, data structures, such as trees and graphs, words, numbers and polynomials. We are interested in their probabilistic analysis, in their random generation as well as in the study of their representation. Our fundamental motivation can be encapsulated in the following questions: What is the behaviour of low-complexity objects ? What does a random object look like ? How to build such objects ? We adopt several perspectives on these questions, from Information Theory and Analytic Combinatorics, to Symbolic Dynamical Systems. The mixing of Analysis of Algorithms and Symbolic Dynamics, complementary subjects, is a distinctive feature of this project.

The base of this project started and evolved during the preceding STIC-AmSud projects (see the previous STIC-AmSud project RAPA2). The interaction is strengthened in this project through the introduction of new partners in Chile. In this sense, we are interested in various problems, such as the complexity of producing digits in one digit base from those in another, sources of zero entropy and data structures on them, and by random sampling. This project is strongly linked to the team “Randomness and Analysis of Algorithms” of the Laboratoire International Associé SINFIN (formerly called INFINIS), Université Paris Diderot-CNRS / Universidad de Buenos Aires-CONICET

Members of EPAA

France

Ali Akhavi, Université de Caen (GREYC)
Valérie Berthé, CNRS and Université Paris-Cité (IRIF)
Julien Clément, CNRS and Université de Caen (GREYC)
Julien David, Université Sorbonne Paris Nord (LIPN)
Matthieu Dien, Université de Caen (GREYC)
Antoine Genitrini, Sorbonne Université (LIP6)
Loı̈ck Lhote, Université de Caen (GREYC)
Frédéric Paccaut, Université de Picardie Jules Verne (LAMFA)
Martin Pépin, Université Sorbonne Paris Nord (LIPN)
Philippe Regnault, Université de Reims Champagne-Ardenne (LMR)
Pablo Rotondo, Université Gustave Eiffel (LIGM)
Brigitte Vallée, CNRS and Université de Caen (GREYC)

Uruguay

Eduardo Canale, Universidad de la República (IMERL) and ANII.
Claudio Qureshi, Universidad de la República (IMERL) and ANII.
Alfredo Viola

Argentina

Nicolás Álvarez, Universidad de Buenos Aires and CONICET (ICC)
Verónica Becher, Universidad de Buenos Aires and CONICET (ICC)
Antonio Cafure, Universidad Nacional de General Sarmiento and CONICET
Eda Cesaratto, Universidad Nacional de General Sarmiento and CONICET
Martı́n Mereb, Universidad de Buenos Aires and CONICET (IMAS)
Martı́n Safe, Universidad Nacional del Sur, Dpto. de Matemática and CONICET

Chile

Paulina Cecchi, Universidad de Chile.
Álvaro Bustos, Pontificia Universidad Católica de Chile.