Thierry Lecroq

Cartesian Pattern Matching

Building Copernic, seminar room (4B125)

Abstract : Cartesian trees are associated to strings of numbers. They are structured as heap and original strings can be recovered by symmetrical traversal of the trees. Let x be a string of numbers of length m. The...[more]

30-Nov-2021

Tom Davot

On a Greedy Approach for Genome Scaffolding

Building Copernic, seminar room (4B125)

Abstract : Scaffolding is a bioinformatics problem aimed at completing the contig assembly process by determining the relative position and orientation of these contigs. It can be seen as a paths and cyc...[more]

23-Nov-2021

Cyril Gavoille

Graphe universel et représentation implicite pour les graphes planaires

Salle de séminaire 4B125, bâtiment Copernic

Résumé: Le nombre de graphes planaires à n sommets (non-isomorphes, non étiquetés) est de l'ordre de c(n+o(n)), où c=O(1). Quel est le plus petit graphe qui les ...[more]

16-Nov-2021

Liat Peterfreund

Grammars for Document Spanners

Seminar room 4B125, Copernic building

Abstract: We propose a new grammar-based language for defining information-extractors from documents (text) that is built upon the well-studied framework of Document Spanners for extracting structured data ...[more]

9-Nov-2021

Vincent Jugé

Sorting presorted arrays

Abstract: Twenty years ago was invented Timsort, a surprisingly efficient sorting algorithm. One crucial aspect of Timsort is that it sorts presorted arrays (rare if array entries are elements of a large set chosen uniformly at random, but frequent in practice...[more]

29-Oct-2021

Romain Couillet

Random matrices could steer the dangerous path taken by AI but even that is likely not enough

Seminar room 4B125 (Copernic building)

Abstract: Like most of our technologies today, AI dramatically increases the world's carbon footprint, thereby strengthening the severity ...[more]

6-Oct-2021

Jonas Ellert

Computing Runs in Strings Over General Ordered Alphabets

A run in a string is a maximal periodic substring. For example, the string "bananatree" contains exactly the runs "anana" and "ee". There are less than n runs in any length-n string, and computing a...[more]

5-Oct-2021

Paweł Gawrychowski

Fully dynamic longest increasing subsequence

We revisit the problem of maintaining the longest increasing subsequence (LIS) of an array under(i) inserting an element, and(ii) deleting an element of an array.In a recent breakthrough, Mitzenmacher and Seddighin [STOC 2020] designe...[more]

28-Sep-2021

Nous avons appris avec grande tristesse le récent décès de Laurent George. Docteur de l’université de Versailles-St Quentin, avec une thèse effectuée à l’INRIA sur l’ordonnancement temps-réel, titulaire d’une HDR de l’université de Nantes, Laurent George était un chercheur et enseignant reconnu. Il ...[more]

7-Jul-2021

Antoine Genitrini, maître de conférences en informatique au LIP6, titulaire d'un doctorat de l'Université de Versailles-Saint-Quentin-en-Yvelines et d'une HDR de l'université Pierre-et-Marie-Curie, est accueilli en délégation CNRS pendant un an au LIGM, pendant l'année universitaire 2020/2021.[more]

3-Nov-2020