Posts classified under: News

On s’intéresse au problème SubIso: étant donnés deux graphes non orientés G et H, déterminer si G contient un sous-graphe qui est isomorphe à H. Le problème SubIso est NP-complet en général. Mais des algorithmes polynomiaux de SubIso existent pour les graphes extra-planaires biconnexes (en O(n3) par ) et pour les SP-graphes biconnexes (en O(n6.5) … Continue reading Séminaire ALGO : Ionona Ranaivoson (GREYC) « Isomorphisme de sous-graphes (SubIso) des graphes séries-parallèles (SP-graphes) et couvertures par trous »

De nos jours, de nombreuses études publient des données sur des bases de données sensibles, mais comment s'assurer qu'elles ne dévoilent pas d'informations sur des individus pris séparément ? Nous allons voir comment nous pouvons concevoir un lambda-calcul dont les fonctions bien typées ne dévoilent aucune information (ou très peu) sur un individu en particulier.

Le problème "Module Learning With Errors" (M-LWE) est une hypothèse calculatoire fondamentale en cryptographie sur les réseaux Euclidiens qui offre un compromis intéressant entre efficacité et sécurité des cryptosystèmes qui en résultent. Ce problème est paramétré par une distribution de secret ainsi qu'une distribution d'erreur. Il y a encore aujourd'hui un fossé entre le choix … Continue reading Séminaire Algo : Corentin Jeudy (Orange Labs, Rennes) « Vers la Difficulté de « Module Learning With Errors » avec Distributions Courtes »

Je commencerai par quelques rappels sur les processus généraux qui produisent des mots, appelés sources, leurs séries génératrices, leur entropie et leur poids de Shannon. Je mentionnerai les sources simples (les sources sans mémoire, les chaînes de Markov). Puis, j’introduirai le modèle des VLMC (= Variable Length Markov Chains) qui se situe juste « au-dessus … Continue reading Séminaire Algo : Brigitte Vallée (GREYC, Caen) « Variations autour du modèle des VLMC (= Variable Length Markov Chains) »

Circuit 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 »

In 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)