Exposés jeunes chercheurs

• Des plages horaires sont prévues de manière à ce que les écoli/er.ère/s puissent présenter leurs recherches. Le but est de faire partager les sujets et de se faire connaître ainsi que de créer des liens, des synergies et des discussions scientifiques. Dans une moindre mesure, il s’agit aussi de faire un exercice de communication scientifique dans un contexte intermédiaire entre le groupe de travail avec les encadrant/e/s de thèses et la communication dans un colloque international.

Ces présentations peuvent se faire sous forme d’exposé et/ou de poster.

La durée de l’exposé peut varier de 5 à 20 minutes selon la demande de l’écoli/er.ère/ et les possibilités de l’emploi du temps. Il est aussi possible de tenter la formule « thèse en 180 secondes ».

Les écoli/er.ère/s seront contactés à ce sujet et invités à participer.

La participation n’est pas obligatoire mais « fortement conseillée ».

Tous vos sujets de recherche sont intéressants, il ne faut pas les cacher !

Merci de contacter les organisateurs en donnant un titre, un résumé ainsi que la modalité de présentation que vous souhaitez.

**************************************************************************************************************

Pacôme Perrotin - "(Dé)composition de Réseaux d'Automates Booléens" slides

On propose un formalisme généralisant les RABs, leur permettant d'avoir des entrées. Ces systèmes se prouvent utiles dans la composition et décomposition de larges réseaux, dont on espère pouvoir examiner certaines propriétés pour un coût réduit. On propose notamment un résultat permettant d'obtenir des réseaux simulateur d'autres réseaux, par le branchement de petits systèmes simulant localement chaque sommet du RAB simulé.

Cédric Bérenger - "Partitionnement équilibré de grilles en zones connexes" slides(html)

Partitionner un réseaux distribué est un moyen simple d'augmenter la bande passante pour des opérations de diffusion / collecte de données: lorsque la taille du réseau augmente, le réseau se scinde en différentes parties, chacune administrée par une nouvelle racine élue.
Cependant, partitionner un réseau en zones connexes de tailles similaires est un problème NP-difficile, même pour des topologies simples comme les grilles carrées.
Pour résoudre ce problème efficacement sans pour autant considérer des topologies adhocs, nous introduisons une sous-famille des grilles carrées (la famille des grilles n-carrées connexes) pour laquelle nous donnons un algorithme de partitionnement en temps polynomial. Cette sous-famille a notamment l'avantage d'être intuitive.
De plus, les instances pratiques que nous considérons sont facilement transformables en instance n-carrées connexes, par ajout et suppression d'un faible nombre de nœuds.

Giovanni Lo Bianco - "Analyse de la structure combinatoire des contraintes de cardinalité" slides

La programmation par contrainte est un paradigme informatique utilisé pour résoudre des problèmes de satisfaction et d’optimisation. Dans un premier temps, il faut rentrer dans un solveur le problème sous forme d’un modèle mathématique, en définissant les variables de décision, leur domaine et les contraintes qui les lient. Le solveur résout ensuite le problème grâce une très large variété d’algorithmes provenant des grands domaines de l’Intelligence Artificielle, la Programmation Logique et la Recherche Opérationnelle.
     Le solveur de contraintes peut être paramétré pour améliorer son efficacité. Selon les instances de problème, un bon paramétrage est essentiel. Nous pensons que ce paramétrage doit prendre en compte la structure combinatoire des contraintes du problème. Nous proposons d’analyser cette structure pour certains types de contraintes, les contraintes de cardinalité, à l’aide d’outils probabilistes et de dénombrement.

Justine Falque - "Orbit Algebra of Oligomorphic Permutation Gr oups withPolynomial Profile, Conjecture of Macpherson"  slides

Define, for $G$ an infinite permutation group, the counting function which mapsany positive integer n to the number of orbits of n-subsets, for the inducedaction of G on the finite subsets of elements.Cameron conjectured that this function, called the profile of G, is aquasi-polynomial in case it is bounded by a polynomial function.Another, stronger conjecture was later made by one of his students, Macpherson.It involves a certain structure of graded algebra on the orbits of
subsetscreated by Cameron, the orbit algebra, and states that if the profile of Gis bounded by a polynomial, then its orbit algebra is finitely generated.The presentation will give an idea of the context of these two conjectures,
some examples, and a sketchy sketch of the proof of Macpherson's conjecture,result of a common work of Nicolas Thiéry and Justine Falque (with preciousadvice from Peter Cameron himself).

Diane Gallois-Wong - "Vérification formelle et filtres numériques" slides

Les algorithmes de filtres numériques sont un outil essentiel du traitement du signal et de la commande. Ils sont généralement définis par des formules mathématiques utilisant des nombres réels ; mais en pratique, leur implémentation utilise nécessairement une arithmétique à précision finie : virgule flottante ou virgule fixe. On obtient alors des erreurs d'arrondi par rapport au modèle initial, qui peuvent s'accumuler au fil des calculs. Étudier ces erreurs pour s'assurer qu'elles restent dans des marges acceptables est très complexe. Comme certains domaines d'application peuvent être critiques, par exemple l'automobile, l'aéronautique ou la robotique, nous souhaitons garantir qu'une implémentation reste suffisamment proche du modèle initial en prouvant formellement des bornes sur les erreurs d'arrondi.

Pierre Mercuriali - "Normal form systems generated by a single connective are equivalent" slides

 In this talk we will focus on the efficient representation of Boolean functions using Normal Form Systems (NFS),that yield sets of terms built using one or several connectives (taken in a specific order), variables and negated variables, and constants. Efficiency is measured in terms of the size (number of connectives) of the terms used to represent a function.

The connectives chosen are those that generate Boolean clones, that are classes of functions stable by composition and that contain all projections. For instance, the clone of all conjunctions Λ is generated by the binary connective ∧. It was proven that the Median NFS associated with the ternary median connective is more efficient than the DNF, CNF, PNF and PᵈNF.

This first study gives rise to several open questions. Are there other such efficient NFS? Which clones/generators yield the most efficient representations? For instance, does the efficiency improve when taking a 5-ary median instead of the ternary one? During this talk we will answer these and several other questions related to the efficiency of NFSs.

Pablo Rotondo - "Continued Logarithm Algorithm: a probabilistic study" slides

Introduced by Gosper in 1978, the Continued Logarithm Algorithm compute s the  gcd of two integers efficiently, performing only shifts and subtractions.Shallit has studied its worst-case complexity in 2016, showing it to belinear. Here, we perform the average-case analysis of the algorithm: we studyits main parameters (number of iterations, total number of shifts) and obtainprecise asymptotics for their mean values, with explicit constants. Our
analysis involves the dynamical system underlying the algorithm, which produces continued fraction expansions whose quotients are powers of 2. Eventhough Chan studied in 2005, this system from an Ergodic Theory perspective,
the presence of powers of 2 in the quotients gives a dyadic flavour which cannot be analysed only with Chan's results. Thus we introduce a dyadiccomponent and deal with a two-component dynamical system. With this new mixed
system at hand, we provide a complete average-case analysis of the algorithm.

Florian Bridoux - "N-complétude dans les réseaux d’automates" slides

On dit qu’un réseau d’automate utilisant un alphabet A est n-complet s’il peut simuler n’importe quelle transformation de A^n avec un certain mode de mise à jour.Dans cette présentation je vais montrer que pour tout alphabet A et pour tout entier n, on peut construire un réseau n-complet de taille n+1, ou un réseau n-complet avec un temps 2n. Il est facile de prouver que le premier est optimal en taille, mais la question de savoir si le deuxième réseau est optimal en temps est encore ouverte.

Titouan Carette - "Un soupçon de catégories servi sur son lit de logique quantique"  slides

 En 1936, dans un papier sobrement intitulé: The logic of quantum mechanics, G Birkhoff et l'omniprésent John Von Neumann développent une idée encore jeune mais à l'avenir radieux: la toute récente formalisation de la mécanique quantique induit une logique d'un genre nouveau. Ces considérations, bien loin de se limiter à la sphère un brin opaque du monde quantique, conduisent à l'introduction de concepts logiques originaux: tout un continuum apparaît entre le vrai et le faux, l'observateur influence l'observé et les opérations logiques ne sont plus si commutatives que ça.

Quentin Brabant - "Polynômes latticiels sur treillis finis"  slides

Les treillis sont des structures algébriques qui apparaissent, implicitement ou explicitement, dans la formulation de nombreux problèmes. Un treillis est défini par l'ensemble de ses éléments et par deux opérateurs, appelés infimum et supremum. Les expressions composées à partir de ces opérateurs, de variables et de constantes, sont appelées polynômes latticiels. Chaque polynôme latticiel exprime une fonction, qui peut être vue comme une opération de "fusion" de valeurs du treillis. J'aborderais le problème suivant : comment trouver un polynôme latticiel qui réalise la fusion d'un nombre fixé de valeurs conformément à un ensemble d'exemples (lorsqu'un tel polynôme latticiel existe) ? Je m'arrêterais plus particulièrement sur le cas où le treillis est distributif.

Ilya Galanov - "On self-assembly of aperiodic tilings" slides

Aperiodic tilings serve as a mathematical model for quasicrystals, such crystals that don't have any translational symmetry (a Penrose tiling is one famous example). The question is how to grow such a tiling just by adding tiles one by one using only the local information (the motivation is to mimic the growth of a real world quasicrystals). In this talk we will propose a local growth algorithm for a particular class of aperiodic tilings (cut-and-project tilings of finite type). We will illustrates this on two examples (namely the Penrose tiling and the Golden-Octagonal tiling).

Renaud Vilmart - "Completeness of the ZX-Calculus" slides

The ZX-Calculus is a powerful graphical language dedicated to quantum computing and reasoning. Its intuitive set of axioms and closeness to circuitry makes it very interesting for anyone working with quantum systems. The main obstacle for its broader use was the lack of completeness results on universal restrictions of the language i.e. its ability to capture all of quantum mechanics. I will present the ZX-Calculus and how we addressed the completeness problem.

Pierre-Adrien Tahay - "Colonnes dans les automates cellulaires" slides

Un automate cellulaire consiste en une grille qui contient dans chaque cellule un élément d’un ensemble fini fixé et qui évolue au cours du temps selon certaines règles locales. En 2015 E. Rowland et R. Yassawi ont montré qu’en regardant certaines colonnes du diagramme espace-temps d'automates cellulaires linéaires, on pouvait y trouver des suites qui sont engendrées par des automates finis. Par ailleurs il est également possible d'obtenir des suites non-automatiques comme colonne d'un automate cellulaire, l'un des exemples les plus connus étant l'indicatrice des nombres premiers. Nous proposerons de construire explicitement des automates cellulaires permettant d'obtenir en colonne l'indicatrice de certains polynômes, qui constituent des exemples de suites non-automatiques.

Bruno Jartoux - "Efficacité de la recherche locale en optimisation combinatoire géométrique" slides

Plus petite couverture par ensembles (ou par sommets), plus grand stable ou plus grand ensemble dominant sont des problèmes d'optimisation difficiles et difficiles à approximer. Pourtant, de façon inattendue, une même heuristique simple fournit un schéma d'approximation en temps polynomial (PTAS) pour leurs restrictions à certains graphes d'intersection d'objets géométriques. L'analyse de cet algorithme repose sur les propriétés des graphes bipartis planaires et « localement » expanseurs, et soulève de nouvelles questions sur les graphes topologiques.

Antoine Grospellier - "Correction efficace d'erreurs pour les codes expanseurs quantiques"  slides

Les codes correcteurs d'erreurs quantiques sont utilisées pour éviter la décohérence des états quantiques. Ils permettent de retrouver l'état initial du système lorsqu'une petite erreur lui a été appliquée. Cet exposé s'intéresse aux "codes expanseurs quantiques" qui ont de nombreuses propriétés intéressantes: ces codes sont LDPC (low density parity check), ont un taux d'encodage non nul, une bonne distance minimale et sont pourvus d'un algorithme de décodage efficace.
Étant donné un code expanseur quantique sur $n$ qubits (un qubit est le support de l'information quantique, c'est l'équivalent du bit classique) et malgré le fait qu'il existe certaines erreurs de poids inférieur à $O(\sqrt{n})$ qui ne sont pas corrigées par l'algorithme de décodage; nous avons montré qu'une erreur de poids inférieur à $O(n)$ est corrigée par ce même algorithme avec grande probabilité.

Charlie Jacomme - "Application des bases de Groebner à la vérification de protocoles cryptographiques"  slides

De nombreux protocoles cryptographiques utilisent l'exponentiation modulaire comme brique de base, et pour les vérifier il peut se poser le problème de la capacité de déduction d'un attaquant : étant donné un ensemble de message que l'attaquant a pu intercepter, est-il capable de déduire un message censé être secret ?
Une fois le problème cryptographique traduit en termes mathématiques, on peut voir apparaître diverses applications des bases de Groebner, qui permettent notamment de tester l'appartenance à un module sur un anneau de polynôme à plusieurs indéterminée ou encore de calculer la saturation d'un module par rapport à un idéal.
Cette exposé présentera donc les origines du problème d'un point de vue haut de niveau vis à vis de la sécurité informatique, la transformation du problème en une version purement mathématiques, et les outils mathématique qui permettent de résoudre ces problèmes.

Florian Liétard - "Evitabilité des k-puissances additives" slides

En combinatoire des mots, les problèmes d'évitabilité sont étudiés depuis le début du siècle dernier à partir des travaux d'Axel Thue. De façon générale il s'agit de savoir si on peut construire des mots aussi grands qu'on le souhaite en utilisant seulement un nombre fini de lettres et qui évitent certains schémas. En 2014, J. Cassaigne, J. Currie, L. Schaeffer et J. Shallit ont montré qu'il était possible de construire sur un alphabet de quatre chiffres un mot infini ne contenant jamais trois blocs consécutifs de même taille et de même somme. Le but ici est de montrer que cette preuve peut être généralisée. En travaillant à partir de morphismes de mots, les résultats obtenus mènent à des critères et à un algorithme qui permet de décider si oui ou non les points fixes générés permettent d'éviter les cubes additifs.

Lydie Richaume - "Dépliement de polycubes - Tours de Manhattan à base H-convexe" slides

Itsaka Rakotonirina - "Verifying equivalence of finite processes"  slides

Careless design choices in security protocols may lead to a user being able to usurp the identity of honest entities, obtain sensible data... How to be sure that the structure of a protocol really prevents sensible data from ending up in unauthorised hands? How to guarantee that malicious users cannot impersonate others? Designing protocols verifying such properties is notoriously hard and humans have proven rather bad at analyzing them by hand. In this work we propose an automated analysis of (in)security. We provide a procedure deciding whether a given security property, formalised by an equivalence statement, is verified by a finite number of sessions of a protocol. The approach is implemented in an automated tool called DEEPSEC, whose applicability has been demonstrated on several case studies.