"Probabilities in Theoretical Computer Science" Year 2023-24 of GDR IFM

Estimating Pi Using Monte Carlo Simulation in R by Andrea Gustafsen

The GDR IFM (Research Group in Theoretical Computer Science and its Mathematics) has dedicated the academic year 2023-2024 to “Probabilities” . The objective is to illustrate the importance of probabilities in computer science and the abundance of contributions from the GDR in their development and potential applications.

In early 2024, a series of actions are planned to commence. These actions will begin with a thematic focus on the various aspects of probability in computer science for the 2024 edition of the Young Researchers School in Mathematical Computer Science. Additionally, working groups within the GDR are encouraged to promote discussions related to the use of probabilities during their thematic days. A dedicated conference is also in the works, along with a prospective report aimed at identifying the means necessary to enhance the French community's expertise in utilizing probabilities within mathematical computer science. Lastly, popularization actions are encouraged, and they will be featured on this page.

Update: The year is now over. Please check the Probability year's report.

Different uses of probabilities

Below is a tentative list of topics in TCS where probabilities are used, primarily as models or resources, but also as new aspects to be modeled in formal methods.

  • Models for analysis, prediction and control. For instance
    • Markov chains
    • Probabilistic transition systems
    • Information theory, algorithmic information theory
    • Limit objects
    • Statistical physics
    • Probabilistic method
  • Computing resources
    • Algorithms
    • Communication
    • Cryptography
    • Distributed computing
  • Formal methods
    • Formal verification of the implementation of probabilistic algorithms
    • Probabilistic domain-specific programming languages
    • Data and knowledge management, uncertainty
    • Applications in biology and medicine
    • Diagnosis, decision making, risk estimation
    • Simulation, digital twin
    • Data analysis

Applications are obviously everywhere in computer science, including computer networks, privacy, social networks, simulation, and prediction, as well as other disciplines such as biology, medicine, and physics

Directly impacted working groups

Below are listed the directly impacted groups (with their name in french and a link to their webpage), categorized within the 3 main axis of the GDR. Nonetheless, all GTs can also contribute to this year if they wish to.

Committee and contact

Below are listed the members of the committee in charge of proposing and programming the events, contacting the concerned GTs, collecting data, and writing the report. The labs and the GTs they are affiliated with are indicated for completeness.

  • Nathalie Bertrand (IRISA): GTs Vérif, DAAL
  • Louis Esperet (GSCOP): GTs Graphes, ALEA, CoA
  • Wenjie Fang (LIGM): GT ALEA
  • Vincent Grosso (LHC): GT C2
  • Bruno Grenet (LJK): GTs Calcul formel, CoA, C2
  • Frédéric Magniez (IRIF): GTs CoA, IQ
  • Michele Pagani (LIP): GTs LHC, Scalp
  • Ovidiu Radulescu (LPHI): GT Bioss
  • Tatiana Starikovskaya (DIENS): GT CoA

Contact the committee via email.

The following will be updated along the year.

Collecting Datas

Popularization

Please send to magniez@irif.fr any popularization events related to this “Probabilities” year. This can be for example any activities in the context of the Fête de la science.

Master's programs and lectures

Please send to magniez@irif.fr any Master's programs and lectures related to probabilities in TCS, or more generated in GDR IFM.

From the GTs

All (relevant) GTs are encouraged to prioritize talks related to this “Probabilities” year during their annual workshop, and to organize dedicated events if they wish to. Support from the GDR can eventually be provided depending on the action.

They are also being contacted to map out research related to probabilities. This survey is conducted via a form that can be filled out with the “Probabilities” committee contact, possibly with assistance from certain group members. The collected information will be centralized on the thematic year's website, including scientific mediation actions and a list of master's programs, and will also be compiled into a prospective report aiming to identify means to enhance the French community's expertise in using probabilities in IFM.

Actions

Young Researchers School in Mathematical Computer Science

The school École Jeune chercheu/r/se/s en Informatique Mathématique 2024 will be organized at Nantes in June 17-21, 2024. Registrations are opened since February 9th. The courses in this edition will focus on topics related to probabilities, within the context of the “Year of Probabilities.” The proposed courses will cover:

  • Verification of probabilistic logics on Markovian decision processes
  • Probabilistic programming languages and their semantics
  • Decomposition of combinatorial objects and their application in probabilities
  • Bioinformatics in a probabilistic framework
  • Complexity and security in a probabilistic context
Keynote talk at GDR days

During the GDR IFM 2024 Days at Grenoble, March 2024, a keynote talk by Guillem Perarnau (Universitat Politecnica de Catalunya) on Wandering on random digraphs was given.

Walks on random graphs has been a subject of extensive research over the past two decades. While the theory is well-established for undirected graphs, the directed case is much less understood.Unfortunately, networks that arise in applications are often inherently directed (e.g. World Wide Web,citation network, …). In recent years, novel techniques have emerged to tackle the complexities in thedirected setting. In this talk we will survey some of the most prominent results in the area concerning randomand non-random walks. We will delve into the mixing properties of the random walks and their (random)stationary measures, providing algorithmic insights. Additionally, we will explore the use of randomdigraphs as a model for random Deterministic Finite Automata (DFA), obtaining a probabilistic version ofČerný's conjecture concerning automata synchronization. The results presented are based on joint work with Xing Shi Cai, Pietro Caputo and Matteo Quattropaniand with Guillaume Chapuy.
Day on Probabilities in Computer Science

A one-day conference is scheduled for September 2024 in the Paris area. The event will feature seven invited talks. Additionally, there will be poster presentations, providing an opportunity for junior researcher (in particular PhD students and postdocs) to showcase their latest research to the audience.

More details

Probabilities year's report

To conclude the year, a report has been written to provide an overview of the thematic year dedicated to probabilities within the GDR IFM. It highlights scientific events (young researchers' school, national conference talks, and a dedicated day at the IHP) and summarizes surveys conducted with several working groups.

The report offers a broad overview of how probabilities are used across the theoretical computer science community, highlights connections between distinct research communities, and formulates recommendations aligned with the challenges identified throughout the year. These recommendations aim to foster research in probabilities within theoretical computer science and to strengthen the positioning of the French community.

The report also serves as a resource to encourage collaborations and initiatives for those interested in the various intersections between probabilities and theoretical computer science.

You can download the "Probabilities in TCS" Year's report.