Posts classified under: Amacc

Current distributed source version-control systems (such as Git and Mercurial), track the history of changes using an append-only directed acyclic graph, sometimes complemented by labels subsequently attached to commits. We present a chain-based and a dichotomy-based framework, both leveraging incremental indices, to answer reachability queries in sub-linear time, and efficiently perform label synchronisation between users. … Continue reading Séminaire Algorithmique : « Commit graphs in Version-Control Systems: incremental reachability and label discovery », Euxane Tran-Girard (LIGM, Univ. Paris-Est G. Eiffel)

La notion de structure transparaît dans de nombreux domaines scientifiques comme une approche pragmatique pour capturer le fait que des objets complexes peuvent être décomposés en éléments plus simples. Nous proposons une formalisation de cette notion et montrons comment s'en servir pour unifier diverses variations des diagrammes de décision binaires (BDD, une représentation simple, pragmatique, … Continue reading Séminaire Algorithmique : « Introduction à la théorie des structures et son application aux fonctions Booléennes », Joan Thibault (IRISA, Rennes)

In this talk, we will explore graphs of shortest paths—directed acyclic graphs (DAGs) derived from shortest path traversals of a graph rooted at a fixed source. After establishing a precise definition of these structures, we will examine methods for uniformly sampling them and investigate their typical shape. Along the way, we will uncover interesting connections … Continue reading Séminaire Algorithmique : « Graphs of Shortest Paths », Mehdi Naima (LIP6, Sorbonne Univ.)

The domatic number of a graph G is the maximum number of pairwise disjoint dominating sets of G. We are interested in the LP-relaxation of this parameter, which is called the fractional domatic number of G. We study its extremal value in the class of graphs of minimum degree d. The fractional domatic number of … Continue reading Séminaire Algorithmique : « Fractional domatic number and minimum degree », Hugo Demaret (Ecole Polytechnique et GREYC)

La méthode de Boltzmann permet de “compiler” un générateur aléatoire uniforme efficace pour les structures discrètes définies par une spécification combinatoire. Après avoir introduit quelques définitions et la méthode, je présenterai notre implémentation de cette méthode : la librairie Python usain-boltz (travail commun avec Martin Pépin). Au fur et à mesure de cette présentation, j’introduirai … Continue reading Séminaire Algorithmique : Matthieu Dien (GREYC, Caen) « Méthode de Boltzmann : quand la génération aléatoire se passe Dien et sans Pépin »

Les diagrammes de décision binaires sont une famille de structures de données permettant de représenter efficacement une fonction booléenne. Ils ont été notamment popularisés par Randal Bryant en 1986 et ont suscité de nombreuses applications. Nous aborderons dans cet exposé quelques questions de comptage sur ces structures en nous concentrant sur la variante la plus … Continue reading Séminaire Algorithmique : Julien Clément (GREYC, Caen) « Compter les diagrammes de décision binaires »

In this work co-written by Louis Jachiet (Télécom Paris), we attempt to answer the following questions: Given that many computer systems are efficient thanks to preprocessing (index calculations in a database, knowledge compilation in AI), which complexity classes with preprocessing are relevant? In this framework, does constant time have any meaning? For this purpose, we … Continue reading Séminaire Algorithmique : Etienne Grandjean (GREYC), « How does preprocessing make it possible to obtain constant time? »

Since recent years, we observe a surge of successful applications of Boolean networks (BNs) in biology and medicine for the modeling and prediction of cellular dynamics in the case of cancer and cellular reprogramming. Such applications face two main challenges: being able to design a qualitative Boolean model which is faithful to the behavior of … Continue reading Séminaire Algorithmique : Sarah Riva (LIFL, Univ. Lille) « Control and synthesis of minimal trap spaces in Boolean Network »

Les string attractors sont des objets combinatoires introduits par Kempa et Prezza dans le but d’unifier différentes mesures de compressibilité de texte provenant de techniques classiques telles que LZ77 ou la transformée de Burrows-Wheeler. Etant donné un texte, un string attractor est un ensemble de positions permettant de capturer tous les motifs apparaissant dans ce … Continue reading Séminaire Algorithmique : France Gheeraert (LAMFA, Univ. Picardie) «String attractors, ou comment capturer la combinatoire d’un texte»

Bitcoin is one of the famous cryptocurrencies in the world. It is a permissionless blockchain, and all transactions are stored in a public decentralized ledger. In its security design, Bitcoin utilizes various cryptographic primitives, such as hash functions and signature schemes. In the current version of Bitcoin, the Elliptic Curve Digital Signature Algorithm (ECDSA) is … Continue reading Séminaire Algorithmique : Michel Seck (Ecole Politech. Thiès, Sénégal) « Towards post-quantum Bitcoin blockchain using Dilithium signature »