Posts classified under: Amacc

Le Générateur Sac à dos, proposé en 1985 par Rueppel et Massey est un générateur pseudo aléatoire (PRNG) qui combine un premier PRNG faible, le LFSR, et un problème dur ,le problème de la somme de sous-ensemble, dérivé du problème de sac à dos. Ce générateur a été attaqué avec succès par Knellwolf et Meyer … Continue reading Séminaire Algorithmique : « Discussion autour du Générateur Sac à dos », Florette Martinez (ENS Ulm)

Nowadays, most of our communications over the Internet are encrypted. However, some cryptographic constructions widely deployed today are vulnerable to quantum attacks, and the goal of post-quantum cryptography is to design classical cryptosystems based on computational problems which remain hard even with the help of quantum computers. In this talk, I will give an introduction … Continue reading Séminaire Algorithmique : « Hardness of the Decoding Problem and its Applications in Post-Quantum Cryptography », Maxime Bombar (CWI, Amsterdam, Pays-Pas)

While rotations are bijections that preserve distances and angles in Euclidean space, these geometric properties are not preserved in general when rotations are applied to digital images. In this talk, we particularlly focus on bijection and topology, which are also generally lost. With regard to bijections, we present the set of rotations that give bijective … Continue reading Séminaire Algorithmique : « How to rotate digital images without losing information? », Yukiko Kenmochi (GREYC, Caen)

Nous montrons dans cet exposé comment obtenir de manière algorithmique un développement asymptotique à tous les ordres pour les systèmes algébriques et donnons quelques clefs pour une généralisation pour certains systèmes différentiellement algébriques.

In 1996, Bruce Reed worked on domination in cubic graphs, and came to the conclusion that 1/3 of the vertices should suffice in dominating connected cubic graphs. Things are not that simple as there are some counter-examples, but the problem still attracted attention (and gave birth to conjectures). In 2008, Lowenstein and Rautenbach made a … Continue reading Séminaire Algorithmique : « Domination in subcubic graphs: swapping numbers », Paul Dorbec (GREYC, Caen)

We carry on the study initiated by Bérard et al. of the reactive synthesis problem for distributed systems with an unbounded number of participants interacting with an uncontrollable environment. Executions of those systems are modeled by data words (i.e. finite or infinite words were positions are labeled by an unbounded alphabet), and specifications are given … Continue reading Séminaire Algorithmique « Synthesis for fragments of first-order logic on data words », Julien Grange (LACL, Univ. Paris-Est Créteil)

History-deterministic automata are intermediary between deterministic and nondeterministic ones, and have been the object of thorough study in the last decade. They offer a way to get a better grasp of the power of nondeterminism, by allowing only some aspects of it: nondeterministic choices are allowed to depend on the past of the computation but … Continue reading Séminaire Algorithmique « History-deterministic and explorable automata », Denis Kuperberg (LIP, ENS Lyon)

A classical result from the theory of formal languages, the Myhill-Nerode theorem, gives a necessary and sufficient condition in terms of congruence classes for a language to be regular. In this talk, we try to adapt this result to the case of subshifts, in which we consider potentially multidimensional infinite configurations rather than finite words. … Continue reading Séminaire Algorithmique : « Computability of extender sets in multidimensional subshifts », Léo Paviet Salomon (GREYC, Caen)

The study of Turing machines as dynamical systems carried several questions that were not considered before, as the question of the existence of an «aperiodicity», finally solved by the very particular machine called SMART. Combined with other techniques, this machine opened the door for a series of new findings. In this talk we will recall … Continue reading Séminaire Algorithmique : « Turing machine dynamics and the SMART machine », Anahi Gajardo (Univ. Conception, Chili)

Vous développez pour un logiciel de gestions de versions, tel Mercurial ou Git ? Et en plus vous aimeriez avoir un moyen de tester vos programmes via des graphes de projet tirés aléatoirement ? Incroyable, cet exposé est fait pour vous ! (et bravo d'exister.) Nous nous intéressons ici à une famille de graphes qui … Continue reading Séminaire Algorithmique : « Génération aléatoire des graphes de Git », Julien Courtiel (GREYC)

Les sous-shifts au langage stable forment une classe de sous-shifts qui a été récemment introduite par V. Cyr et B. Kra. Cette famille contient de nombreux exemples classiques de sous-shifts, de diverses complexités allant des systèmes d’entropie strictement positive, comme les sous-shifts de type fini, aux systèmes de faible complexité, comme les sous-shifts de complexité … Continue reading Séminiare Algorithmique « Sous-shifts au langage stable », Samuel Petite (LAMFA, Univ. Picardie)

Malgré la popularisation de langages modernes qui permettent une gestion sûre de la mémoire, C et C++ restent des langages de choix pour le développement de nombreux logiciels très couramment utilisés. Si ces langages permettent d'obtenir de bonnes performances, ils sont particulièrement vulnérables aux attaques par corruption mémoire.  Des études récentes estiment que des erreurs … Continue reading Séminaire Algorithmique : « StarMalloc : un allocateur de mémoire moderne renforcé formellement vérifié », Antonin Reitz (équipe Prosecco, INRIA Paris)