AMACC

AMACC Team

Algorithms, calculation Models, Alea, Combinatorics, Cryptography, Complexity

INTRODUCTION

Team leader: Paul DORBEC

The AMACC team is characterized by a strong cultural identity: mathematical computation. The team is interested by two generic concepts,  algorithm and complexity, covering all of its research activities. It adopts complementary viewpoints. On one hand, one studies calculation models and complexity notion, through the classes of complexity. On the other hand, one works within a randomness framework, with probability models, notably using it as a tool for average-case complexity analysis.

Keywords: mathematic computation, calculation models, complexity, cellular automate, RAM machines, dynamic analysis of algorithms, Euclidian algorithms, lattices, text algorithms, bijective combinatorics, analytic combinatorics, cryptography.

RESEARCH TOPICS

Analysis of algorithms

The aim is to study the average-case, as well as the worst-case complexity of algorithms. Complexity is a study of the algorithm in relation to all of its input data. To study the average-case complexity of an algorithm, it is necessary to represent the possible inputs as a whole. This can be done by enumerating the objects under study, or by considering a probabilistic model of these data.

The team is also interested in algorithm models, defining the algorithm as a dynamical system, and in the creation or improvement of algorithms.

Description of problems

When studying a problem, we also talk about complexity, in the sense of complexity theory. This involves studying the problem in relation to all the algorithms that can process it. We are interested in the different complexity classes (the most well-known being P and NP), regardless of the specific nature of each algorithm. Problems that are difficult to solve have, in particular, applications in cryptography.

The study of problem complexity also draws on computational models and logic.

Study of input data

The data is studied here as combinatorial objects, such as words, trees or graphs. In particular, the focus is on the structural properties of these objects, their enumeration (in the sense of counting) and their generation. The team also studies the entropy of a data set, which reflects the amount of information needed to model the diversity of possible data.

FOR MORE INFORMATION

Permanent members

CLÉMENT Julien – CNRS researcher, HDR

COURTIEL Julien – Associate professor, UNICAEN

DAVID Julien – Associate professor, HDR, UNICAEN

DIEN Matthieu – Associate professor, UNICAEN

DORBEC Paul – Professor, UNICAEN

LHOTE Loïck – Professor, ENSICAEN

PÉPIN Martin – Associate professor, UNICAEN

RANAIVOSON Solomanpionona – Associate professor, UNICAEN

RICHARD Gaétan – Associate professor, UNICAEN

ROUX-LANGLOIS Adeline – CNRS Research Director

TERRIER Véronique – Associate professor, HDR, UNICAEN

VANIER Pascal – Professor, UNICAEN

Non-permanent members

BEAUGRAND Agathe – Temporary Research and Teaching Assistant (CTER), PhD

BERGERAT Loris – PhD student (CIFRE)

CANARD Sébastien – partner

DEMARET Hugo – PhD student

DOUTEAU Antoine – PhD student

GRANDJEAN Etienne – Emeritus professor

GRENTE Théo – Temporary Research and Teaching Assistant (CTER), PhD

KARCZMARCZUK Jerzy – Associated researcher

MITTELSTAEDT Arthur – PhD student

REPEL Émeline – PhD student

VALLÉE Brigitte – CNRS Emeritus Research Director

Projects

AMIRAL ANR-ASTRID Project: AMélioration des sIgnatures reposant sur les Réseaux et Applications aux fonctionnaLités cryptographiques avancées, 2022-2026. Principal Investigator: Adeline Roux-Langlois; Local participants: Adeline Roux-Langlois and Émeline Repel.

EPAA STIC AmSud Project (Entropy and Probabilistic Analysis in Algorithms), 2024-2025 (France, Uruguay, Argentina). Local participants: Julien Clément, Julien David, Matthieu Dien, Loïck Lhote, Martin Pépin, and Brigitte Vallée.

Lyndex Project: project founded by the Fédération Normastic around the study of Lyndon words. Local members: Julien Clément and Julien David.

PAnDAG ANR Project : French-Austrian project dedicated to the study of parameters of interest in DAGs, 2024-2027. Principal Investigator: Antoine Genitrini; Local coordination: Julien Clément; Local participants: Julien Clément, Julien Courtiel, Matthieu Dien, and Martin Pépin.

PLASMA ANR Project : Programming Languages, Algorithms and Structures: Models and Analysis, 2026-2030. Principal Investigator: Cyril Nicaud; Local participants: Julien Clément, Julien Courtiel, Julien David, Matthieu Dien, Martin Pépin, and Brigitte Vallée.

PQ-TLS PEPR Project: Post-quantum padlock for web browser, 2022-2027. Local participant: Adeline Roux-Langlois.

Participation to SINFIN, an International Research Project (IRP) with Argentina in which we co-lead the Randomness and Analysis of Algorithms team. Local participants: Julien Clément, Julien David, Matthieu Dien, Loïck Lhote, Martin Pépin, and Brigitte Vallée.

Collaborations

Normandy: AlgoComb axis of the NormaStic CNRS federation.

France: GDR IFM and GDR Securité

Inrenational: Strong interactions with South America (Argentina, Uruguay)

Software

ThemaMap project: multi-platform thematic mapping tool, distributed as open-source software. It is developed in collaboration by GREYC, SAIC-CERTIC and CRH.

Usain Boltz, by Matthieu Dien and Martin Pépin. A Python library for the efficient random generation of large data structures with uniformity guaranties.

VOIR LES PUBLICATIONS

TEAM LIFE

Work group

The team also meets almost periodically in a Groupe de Lecture et de Travail (GLT).
URL: https://glt-amacc.greyc.fr/

Seminar

The team has been running and organizing the weekly Algorithmics seminar for some twenty years now.

URL: https://clementj01.users.greyc.fr/semalgo/

KEY FACTS