Séminaire Algorithmique : Mostafa Gholami (GREYC, Caen) « Multicolor bipartite Ramsey numbers for paths, cycles, and stripes »
Sciences 3- S3 351Frank Ramsey introduced the theory that bears his name in 1930. The main subject of the theory are complete graphs whose subgraphs can have some regular properties. Most commonly, we look for monochromatic complete subgraphs, i.e., complete subgraphs in which all of the edges have the same color. Ramsey numbers have attracted the attention of … Continue reading Séminaire Algorithmique : Mostafa Gholami (GREYC, Caen) « Multicolor bipartite Ramsey numbers for paths, cycles, and stripes »
Séminaire Algorithmique : Pierre Béaur (LISN, Université Paris-Saclay) « Walking On a Line: détection de marches S-adiques dans les ω-automates »
Sciences 3- S3 351En dynamique symbolique s'intersectent études des langages, des mots infinis et des structures dynamiques associées. Deux méthodes classiques de construction de ces objets coexistent. D'abord, la méthode de Thue construit un mot infini à l'aide d'une substitution (un morphisme de mots) : on itère la substitution sur une lettre initiale, et on considère le mot … Continue reading Séminaire Algorithmique : Pierre Béaur (LISN, Université Paris-Saclay) « Walking On a Line: détection de marches S-adiques dans les ω-automates »
Séminaire Algorithmique : “Robustness of the RAM model” or “how to perform a division in constant time”, Etienne Granjean (GREYC, Caen)
Sciences 3- S3 351Accurately measuring the complexity of algorithms and establishing the intrinsic computational complexity of problems are among the most important tasks/goals in computer science. For this, everyone agrees that the right model of computation (for sequential algorithms) is the random access machine (RAM). Contrary to this general agreement, paradoxically, there is no consensus on how to … Continue reading Séminaire Algorithmique : “Robustness of the RAM model” or “how to perform a division in constant time”, Etienne Granjean (GREYC, Caen)
Séminaire Algorithmique : Ana Maria Costache (NTNU, Trondheim, Norvège) « FHE Circuit Privacy for Free »
Sciences 3- S3 351Circuit privacy is an important notion in Fully Homomorphic Encryption (FHE), well-illustrated by the Machine Learning-as-a-Service scenario. A scheme is circuit private if an adversary cannot learn the circuit evaluated on a ciphertext from the computation result. In this talk, we show that the FHE scheme BGV is computationally circuit private in a semi-honest context. … Continue reading Séminaire Algorithmique : Ana Maria Costache (NTNU, Trondheim, Norvège) « FHE Circuit Privacy for Free »
Séminaire Algorithmique : « Ten asymptotic expansions for the Stirling numbers of the second kind » Hsien-Kuei Hwang (Academia Sinica, Taipei, Taiwan)
Sciences 3- S3 351In this talk, I will first review existing asymptotic approximations in the literature for the Stirling partition numbers (or Stirling numbers of the second kind), the list of references being by far the most complete one. Then I will present a general, systematic, elementary approach to generate ten different asymptotic expansions whose uniformity covers particularly … Continue reading Séminaire Algorithmique : « Ten asymptotic expansions for the Stirling numbers of the second kind » Hsien-Kuei Hwang (Academia Sinica, Taipei, Taiwan)
Séminaire Algorithmique : « The structure of quasi-transitive graphs avoiding a minor with applications to the Domino Conjecture », Ugo Giocanti (G-Scop, Univ. Grenoble)
Sciences 3- S3 351An infinite graph is quasi-transitive if the action of its automorphism group on its vertex set has finitely many orbits. Roughly speaking, this means that the graph has a lot of symmetries. Starting with the work of Maschke (1896), a lot of work have been done on the structure of planar Cayley graphs,and more generally … Continue reading Séminaire Algorithmique : « The structure of quasi-transitive graphs avoiding a minor with applications to the Domino Conjecture », Ugo Giocanti (G-Scop, Univ. Grenoble)
Séminaire Algorithmique : « Une extension probabiliste de la suite d’Oldenburger-Kolakoski », Irène Marcovici (LITIS, Univ. Rouen)
Sciences 3- S3 351La suite d’Oldenburger-Kolakoski est l’unique suite infinie sur l’alphabet {1,2} qui commence par un 1 et est un point fixe de l’application de codage par plage. Dans cet exposé, nous prendrons un peu de recul par rapport à cette suite bien connue et très étudiée, en introduisant de l’aléa dans le choix des lettres écrites. … Continue reading Séminaire Algorithmique : « Une extension probabiliste de la suite d’Oldenburger-Kolakoski », Irène Marcovici (LITIS, Univ. Rouen)
Séminaire Algorithmique : « FHE & AI: a Concrete Use-Case », Bastien Vialla (Orange Labs, Caen)
Sciences 3- S3 351In the Franco-German collaborative project CRYPTECS, Orange Innovation explores privacy-preserving technologies for industrial applications. A prime use-case is detecting compromised computers through network traffic analysis. We have developed efficient AI models tailored for this. Our aim is to deploy these models while safeguarding both the model and network data, making Fully Homomorphic Encryption (FHE) an … Continue reading Séminaire Algorithmique : « FHE & AI: a Concrete Use-Case », Bastien Vialla (Orange Labs, Caen)
Séminaire Algorithmique : « Bornes Inférieures et Séparations pour la Compilation de Connaissances Bottom-Up », Alexis de Colnet (CRIL, Univ. Lens)
Sciences 3- S3 351La compilation de connaissances est un domaine de l’informatique qui étudie les différentes classes de représentations pour les fonctions, et les algorithmes permettant de passer d’une classe à l’autre. Dans cette présentation, on s’intéresse à l’approche de compilation dite bottom-up (ascendante) pour les fonctions Booléennes données comme des formules CNF. Cette approche permet de construire … Continue reading Séminaire Algorithmique : « Bornes Inférieures et Séparations pour la Compilation de Connaissances Bottom-Up », Alexis de Colnet (CRIL, Univ. Lens)
Séminaire Algorithmique : « Samplelim: un package R pour l’échantillonnage de solutions à un problème linéaire inverse »,Théo Grente (LMNO, Caen)
Sciences 3- S3 351Utilisés notamment en écologie marine, les réseaux trophiques sont une représentation sous forme de graphes dirigés et pondérés des interactions proies/prédateurs d’un écosystème. Les nœuds du graphe représentent alors les espèces et les arêtes leurs interactions sous forme d’échanges de matière organique appelés flux. Dans le but d’estimer la valeur de ces flux, une classe … Continue reading Séminaire Algorithmique : « Samplelim: un package R pour l’échantillonnage de solutions à un problème linéaire inverse »,Théo Grente (LMNO, Caen)
Séminaire Algorithmique : « Tough graphs and Hamiltonian degree conditions », Cléophée Robin (GREYC, Caen)
Sciences 3- S3 351A graph G is Hamiltonian if it exists a cycle in G containing all vertices of G exactly once. A graph G is t-tough if, for all subsets of vertices S, the number of connected components in G − S is at most |S| / t. We extended a theorem of Hoàng by proving the … Continue reading Séminaire Algorithmique : « Tough graphs and Hamiltonian degree conditions », Cléophée Robin (GREYC, Caen)
Séminaire Algorithmique : « Percolation Bootstrap (ou d’amorçage) sur les pavages de Penrose », Victor Lutfalla (I2M, Univ. Marseille)
Sciences 3- S3 351Les pavages de Penrose sont des pavages non-périodiques du plan par losanges. Dans cet exposé, je vais présenter la percolation dynamique sur ces pavages, c’est-à-dire un processus de contamination sur ces pavages depuis une configuration initiale aléatoire. Étant donné un pavage de Penrose, on met sur chaque tuile un état 0 ou 1. On fait … Continue reading Séminaire Algorithmique : « Percolation Bootstrap (ou d’amorçage) sur les pavages de Penrose », Victor Lutfalla (I2M, Univ. Marseille)