Posts classified under: Amacc

Les règles de votes multi gagnants ont de multiples applications (1er tour d'élection, concours de différentes sortes, choix de produits à promouvoir pour une entreprise...). Elles sont cependant moins étudiées que les règles qui n'élisent qu'un gagnant. En partant de l'étude axiomatique de certaines de ces règles, nous nous sommes interrogés sur la similarité des … Continue reading Séminaire ALGO : Marin Gohard (CREM, Univ. Caen) « Les règles de vote multi gagnants : Une proximité axiomatique est-elle liée à des résultats similaires ? »

Dans la recherche actuelle de primitives pouvant résister à l’utilisation d’un ordinateur quantique, une des pistes majeure se base sur les réseaux euclidiens, et, en particulier, sur le problème Learning With Errors (LWE). En effet, il existe une réduction pire cas - moyen cas vers le problème classique de réseaux qu’est le Shortest Vector Problem … Continue reading Séminaire Algo : Andrea Lesavourey (IRISA, Rennes) « Recherche d’éléments courts dans les réseaux idéaux »

A context-free language is inherently ambiguous if any grammar that recognizes it is ambiguous, i.e. there exists a word that is generated in two different ways. Deciding the inherent ambiguity of a context-free language is a difficult problem, undecidable in general. The first examples of inherently ambiguous languages were discovered in the 1960s, using iteration … Continue reading Séminaire Algorithmique : Florent Koechlin (LORIA, Nancy) « Two new criteria to prove the inherent ambiguity of bounded context-free languages »

Betweenness centrality has been a long subject of study in network science since it was introduced by Freeman in 1977. This centrality measure assesses the importance of nodes in a graph, it has been used for example in social, biological and research collaboration networks. Moreover, betweenness centrality has been used in graph partitioning and community … Continue reading Séminaire Algorithmique : Mehdi Naima « Extending Brandes algorithm to improve betweenness centrality computation in temporal graphs with discrete and continuous time »

Résumé : Le problème de la Dimension Métrique d’un graphe se pose de la façon suivante : on cherche un ensemble R de sommets de taille minimale tel que, pour toute paire de sommets du graphe, il existe un sommet de R dont les distances aux deux sommets de la paire sont distinctes. Ce problème … Continue reading Séminaire Algorithmique : « Algorithmes pour la Dimension Métrique dans les graphes dirigés » Antoine Dailly (LIMOS, Univ. Clermont-Ferrand)

Attention ! Exceptionnellement, le séminaire à lieu lundi à 14h. Résumé : Complexité des jeux positionnels Les jeux positionnels sont des jeux à deux joueurs joués dans un hypergraphe. Les joueurs sélectionnent alternativement des sommets de l'hypergraphe et les conditions de victoires dépendent uniquement du remplissage des hyperarêtes. Le morpion est un exemple célèbre de … Continue reading Séminaire Algorithmique : « Complexity of positionnal games » Valentin Gledel (Univ. Umea, Suède)

The sum of digits function in base 2, also called the Hamming weight, is the number of non-zero binary digits of an integer. This function is a central object for all my present research and appears in many scientific fields, such as number theory, combinatorics on words, and coding theory. In this talk, I will … Continue reading Séminaire Algo : Pierre Popoli (LORIA, Univ. de Lorraine) « Sum of digits, pseudorandomness and measures of complexity »

Directed Acyclic Graphs (DAGs) are directed graphs in which there is no path from a vertex to itself. They are an omnipresent data structure in computer science and the problem of counting the DAGs of given number of vertices has been solved in the 70’s by Robinson. In this talk, I will introduce a new … Continue reading Séminaire Algorithmique : Martin Pépin (LIPN, Univ. Paris Nord) « Directed Ordered Acyclic Graphs, asymptotic analysis and efficient random sampling »

Silvère Gangloff (Univ. AGH, Cracovie, Pologne) « Classes de transitivité pour les sous-décalages de type fini multi-dimensionnels » Ce travail est en commun avec B. Hellouin et P. Oprocha. Les sous-décalages de type fini multidimensionnels ont été étudiés dans les dernières décennies à travers le spectre de propriétés topologiques telles que la transitivité ou le … Continue reading Séminaire Algorithmique: ANNULÉ EN RAISON DU MOUVEMENT DE GRÈVE