Évènements

Les frameworks de preuves “Engager-et-prouver” sont une généralisation des protocoles à divulgation nulle de connaissances. Ils permettent, en plus de prouver la connaissance d’un élément secret à un tiers, de prouver certaines propriétés et relations. Par exemple, qu’un vecteur est de petite norme ou encore qu’il est solution d’une relation quadratique publique. Un de ces … Continue reading Séminaire Algorithmique : « Rejection-free framework of Zero-Knowledge Proof », Antoine Douteau (GREYC, Caen)

The problem Matching Cut asks for an edge set of a graph which is both an edge cut and a matching. An edge cut is a set of edges whose deletion disconnects the graph and a matching is a set of edges in which no two edges share an endpoint. We consider the two recent … Continue reading Séminaire Algorithmique : « Optimising Matching Cuts », Félicia Lucke (LIP, ENS Lyon)

Given a graph G, a dominating set of G is a subset of vertices S such that every vertex not in S is adjacent to at least one vertex in S; that is, NG = V(G). While classical studies focus on finding the smallest dominating set of G, our focus shifts to finding the maximum … Continue reading Séminaire Algorithmique : « Packing many dominating sets in a graph », François Pirot (LISN, Univ. Paris-Saclay)

The Conforti–Cornuéjols conjecture has remained open for 36 years. In this talk, we present a criterion for a minimal counterexample to the Conforti–Cornuéjols conjecture. This talk is based on the following published paper: Bretto, Alain; Nasernejad, Mehrdad; Toledo, Jonathan. On the strong persistence property and normally torsion-freeness of square-free monomial ideals. Mediterr. J. Math. 22 … Continue reading Séminaire Algorithmique : « A criterion for a minimal counterexample to the Conforti–Cornuéjols conjecture », Mehrdad Nasernejad (GREYC, Caen)

De tout temps, femmes et hommes ont aspiré à des nano-colifichets en ADN. Depuis les années 1990, dans la suite des travaux séminaux de Reif, Adleman, Winfree, puis Rothemund et tant d’autres, ils et elles sont exaucés: par une conception astucieuse de mots sur l’alphabet {A, C, T, G}, il est possible d’obtenir des séquences … Continue reading Séminaire Algorithmique : « Géométrie et calcul dans l’auto-assemblage: formes fractales et théorème de l’espalier », Florent Becker (LIFO, Univ. Orléans)

Elastic degenerate strings provide a flexible framework for representing sequences with structured variability, generalizing classical string models while preserving algorithmic tractability. In this talk, we present a comprehensive framework for indexing such objects, culminating in the construction of an FM-index that supports efficient pattern matching. We begin by revisiting the notion of elastic degeneracy and … Continue reading Séminaire Algorithmique : « From Elastic Degenerate Strings to Full-Text Indexing: Suffix Sorting, BWT, and FM-Index Construction and Search », Francesco Pio Marino (Univ. Catane, Italie)