BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen - ECPv5.7.0//NONSGML v1.0//EN
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
X-ORIGINAL-URL:https://www.greyc.fr
X-WR-CALDESC:évènements pour GREYC UMR CNRS 6072 - Groupe de Recherche en Informatique, Image, et Instrumentation de Caen
BEGIN:VTIMEZONE
TZID:Europe/Paris
BEGIN:DAYLIGHT
TZOFFSETFROM:+0100
TZOFFSETTO:+0200
TZNAME:CEST
DTSTART:20230326T010000
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0200
TZOFFSETTO:+0100
TZNAME:CET
DTSTART:20231029T010000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20230306T140000
DTEND;TZID=Europe/Paris:20230306T150000
DTSTAMP:20260423T123627
CREATED:20230213T105713Z
LAST-MODIFIED:20230303T085551Z
UID:11098-1678111200-1678114800@www.greyc.fr
SUMMARY:Séminaire Algorithmique : « Complexity of positionnal games » Valentin Gledel (Univ. Umea\, Suède)
DESCRIPTION:Attention ! Exceptionnellement\, le séminaire à lieu lundi à 14h.\nRésumé : Complexité des jeux positionnels\nLes 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 jeu positionnel\, les lignes\, colonnes et diagonales formant les hyperarêtes et le premier joueur à remplir une hyperarête gagnant la partie. Les jeux positionnels sont étudiés depuis leur introduction par Hales et Jewett en 1963\, puis popularisée par Erdős and Selfridge in 1973 et ont conservé jusqu’à aujourd’hui un vif intérêt.\nCependant\, même si la convention Maker-Breaker\, forme la plus étudiée des jeux positionnels\, a été prouvée comme étant PSPACE-complet par Schaefer en 1978\, beaucoup de problèmes restaient ouverts concernant la complexité des jeux positionnels. En particulier\, la complexité de la convention Avoider-Enforcer restait ouverte et les jeux positionnels et leur complexité étaient peu considérée sur des classes plus restreintes d’hypergraphes. Cette présentation commencera par une introduction aux jeux positionnels avec un aperçu des résultats principaux du domaine. Puis\, nous donnerons une ébauche de preuve pour la PSPACE-completude de la convention Avoider-Enforcer récemment prouvée. Enfin\, nous complèterons cette présentation en étudiant les jeux positionnels en lien avec des problèmes de graphes et la complexité de tels problèmes. \nAbstract: Complexity of positionnal games\nPositional games are two-player games played on a hypergraph. The players alternate selecting vertices of the hypergraph\, and the winning conditions depend solely on the filling of the hyperedges. Tic-tac-toe is a famous example of a positional game\, with the rows\, columns\, and diagonals forming the hyperedges and the first player to fill a hyperedge winning the game. Positional games have been studied since their introduction by Hales and Jewett in 1963\, and were popularized by Erdős and Selfridge in 1973. They still remain of great interest today.\nHowever\, even though the Maker-Breaker convention\, the most studied form of positional games\, was proven to be PSPACE-complete by Schaefer in 1978\, many problems remained open regarding the complexity of positional games. In particular\, the complexity of the Avoider-Enforcer convention remained open\, and positional games and their complexity were little considered on more restricted classes of hypergraphs. In this presentation\, we will discuss recent advances in the study of the complexity of positional games\, including new results on the Avoider-Enforcer convention and on positional games on restricted classes of hypergraphs. This presentation will begin with an introduction to positional games\, providing an overview of the main results in the field. Then\, we will give a proof sketch for the recently proven PSPACE-completeness of the Avoider-Enforcer game. Finally\, we will conclude this presentation by studying positional games in relation to graph problems and the complexity of such problems. \n(déplacé à ce lundi en raison de la grève du 7 mars)
URL:https://www.greyc.fr/event/seminaire-algorithmique-valentin-gledel-univ-umea-suede/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,Séminaire Algo
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20230320T153000
DTEND;TZID=Europe/Paris:20230320T163000
DTSTAMP:20260423T123627
CREATED:20230310T134335Z
LAST-MODIFIED:20230310T134618Z
UID:11135-1679326200-1679329800@www.greyc.fr
SUMMARY:Séminaire Algo : Pierre Popoli (LORIA\, Univ. de Lorraine) « Sum of digits\, pseudorandomness and measures of complexity »
DESCRIPTION: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 present how this function is a central object of my research. \nThe first part of my research work focused on generating pseudorandom sequences from non-random ones. Pseudorandom sequences are generated by a deterministic algorithm and behave like random sequences. Many scientific fields use pseudorandom sequences\, such as cryptography for a cryptographic key generation or numerical integration for Monte Carlo methods. One of the challenges of this research area is to generate a pseudorandom sequence efficiently. In particular\, automatic sequences are generated by an automaton\, and their structures are deterministic. The Thue-Morse sequence\, the sum of digits function in base two modulo 2\, is the most well-known example of an automatic sequence. We use indicators called measures of complexity to qualify a sequence of pseudorandom. My two first papers deal with the maximum order complexity of a sequence\, namely the length of the shortest Feedback Shift Register (FSR) that generates the sequence. This measure of complexity evaluates if a sequence is predictable and suitable for cryptographic applications. In the first paper\, I proved a lower bound on the maximum order complexity of polynomial subsequences of the Thue-Morse sequence\, depending on the degree of the polynomial. In a second paper\, with D. Jamet and T. Stoll\, we study the analog of the Thue-Morse sequence in the Zeckendorf numeration system based on the Fibonacci sequence. The sum of digits function in this numeration system is close to the one associated with the Thue-Morse but has very different properties. Hence\, we proved a lower bound for the maximum order complexity of these sequences along polynomial subsequences. Still\, this result differs slightly from the previous one since the carry propagation works differently. \nThe second part of my research deals with specific Diophantine equations related to the sum of digits function in base two. Firstly Bennett\, Bugeaud\, and Mignotte (2012) have proved that there is only a finite number of perfect odd squares with four binary digits. Also\, they conjectured that the set of solutions is 13\,15\, 47\, and 111. In a recent paper\, we have proved that this conjecture is true for odd integers with at most 17 non-zero binary digits and a similar result for the case of perfect odd squares with five binary digits. Secondly\, Hare\, Laishram\, and Stoll (2012) studied odd integers with the same number of bits as their square\, and they proved a global result for most cases. Finally\, we have proved most of the remaining cases in the same paper. The proofs rely on elementary properties of the sum of digits function\, combinatorics\, and two efficient algorithms. This paper is a joint work with Aloui\, Jamet\, Kaneko\, Kopecki\, and Stoll.
URL:https://www.greyc.fr/event/seminaire-algo-pierre-popoli-loria-univ-de-lorraine-sum-of-digits-pseudorandomness-and-measures-of-complexity/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,Séminaire Algo
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20230321T100000
DTEND;TZID=Europe/Paris:20230321T110000
DTSTAMP:20260423T123627
CREATED:20230213T105826Z
LAST-MODIFIED:20230310T144055Z
UID:11100-1679392800-1679396400@www.greyc.fr
SUMMARY:Séminaire Algorithmique : Martin Pépin (LIPN\, Univ. Paris Nord) « Directed Ordered Acyclic Graphs\, asymptotic analysis and efficient random sampling »
DESCRIPTION: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. \nIn this talk\, I will introduce a new class of DAGs (DOAGs for Directed Ordered Acyclic Graphs)\, endowed with an independent ordering of the children of each vertex. They offer a new modelisation tool for objects arising from the compaction of tree-like structures. \nFor this class we obtain a recursive decomposition scheme that is amenable to effective random sampling with control over the number of edges\, an optimised sampler for the case when the number of edges is free\, and prove an unusual asymptotic behaviour. I will also show that our approach also applies to classical DAGs\, thus providing a solution to the problem of sampling DAGs with a prescribed number of edges.
URL:https://www.greyc.fr/event/seminaire-algorithmique-martin-pepin-lipn-univ-paris-nord/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,Séminaire Algo
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=Europe/Paris:20230328T100000
DTEND;TZID=Europe/Paris:20230328T110000
DTSTAMP:20260423T123627
CREATED:20230213T105951Z
LAST-MODIFIED:20230327T121726Z
UID:11102-1679997600-1680001200@www.greyc.fr
SUMMARY:Séminaire Algorithmique: ANNULÉ EN RAISON DU MOUVEMENT DE GRÈVE
DESCRIPTION:Silvère Gangloff (Univ. AGH\, Cracovie\, Pologne) « Classes de transitivité pour les sous-décalages de type fini multi-dimensionnels » \nCe 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 mélange. Dans des travaux récents\, nous avons montré\, avec B. Hellouin et M. Sablik\, qu’en quantifiant ces propriétés\, il est possible de caractériser la complexité de ces systèmes dynamiques en fonction de la quantité de transitivité/mélange (en particulier du point de vue calculabilité). Cependant les différentes classes de transitivité (relatives à cette quantification) sont mal comprises dans le cas général. Avec B. Hellouin et P. Oprocha\, nous travaillons à caractériser ces classes dans le cadre restreint des Hom shifts\, c’est-à-dire les sous-décalages définis par des ensembles de motifs interdits consistant en des dominos dont les symboles ne sont pas voisins dans un graphe fini non-orienté. Dans cet exposé\, je présenterai le problème\, ainsi que des résultats obtenus et attendus dans cette direction\, qui laissent espérer une caractérisation complète des classes de transitivité dans le cas des Hom shifts.
URL:https://www.greyc.fr/event/seminaire-algorithmique-silvere-gangloff-univ-agh-cracovie-pologne/
LOCATION:Sciences 3- S3 351
CATEGORIES:Amacc,General,Séminaire Algo
END:VEVENT
END:VCALENDAR