Tag: Team seminar
Complexité du problème de distance d’édition minimum à un line-digraphe
summary: La distance d'édition est une mesure classique utilisée pour évaluer la proximité entre un graphe donné et un autre graphe ou une classe de graphes. Cette distance représente le nombre minimum de modifications requises pour transformer le graphe initial en un graphe appartenant à la classe voulue. Une ...
Skipless chain decompositions and improved poset saturation bounds
summary: We show that given m disjoint chains in the Boolean lattice, we can create m disjoint skipless chains that cover the same elements (where we call a chain skipless if any two consecutive elements differ in size by exactly one). By using this result we are able to answer ...
Asymptotic behaviour of cyclic automata
summary: Cyclic dominance describes models where different states (species, strategies...) are in some cyclic prey-predator relationship: for example, rock-paper-scissors. This occurs in many contexts such as ecological systems, evolutionary games on graphs, etc. Many models exhibit heteroclinic cycles where one state dominates almost the whole space before being replaced by ...
La boîte aux lettres avait des dents : propriétés des pièges à facteurs dans le cas bi-infini
summary: En 2017, en algorithmique de texte, Prezza a introduit la notion de piège à facteurs : pour un mot fini w, un piège à facteurs pour w est un ensemble E de positions de w telles que pour tout facteur f de w, il existe une position de E qui ...
Complexity of neural network training and complexity proofs bypassing frontier issues
summary: We study the complexity of the neural network training decision problem in two different contexts. First, in the general context, this problem has been shown to be in extensions of the class ∃R. We have been able to show that whenever the activation functions are Lipschitz functions and the ...
Étude énumérative des intervalles dans les treillis de type Tamari
summary: Le treillis de Tamari est un ordre partiel sur les objets Catalan. De nombreuses descriptions de ce treillis donnent lieu à de nombreuses familles de généralisations, notamment les treillis m-Tamari, nu-Tamari et m-Cambriens. Après une "visite guidée" dans ce zoo des généralisations du treillis de Tamari, je présenterai mon ...
Edge k-q-colorability of graphs
summary: Given positive integers k, q, we say that a graph is edge k-q-colorable if its edges can be colored in such a way that the number of colors incident to each vertex is at most q and that the size of a largest color class is at most k ...
The freezing threshold for uniformly random colourings of sparse graphs
summary: Given a random Δ-regular graph G, it holds that χ(G) ~ Δ / (2 ln Δ) with high probability. However, for any ε > 0 and k large enough, no (randomised) polynomial-time algorithm returning a proper k-colouring of such a random graph G is known to exist when k < (1−ε ...
Musical juggling: from combinatorial modeling to computer assistance with artistic creation (a thesis in the making)
summary: Musical juggling consists of producing music by the very act of juggling. In this context (stemming from a
collaboration between computer science researchers at LISN and a juggling artist), we refer more specifically to
juggling with balls that each produce a musical note when caught.
The aim of this ...
The χ-binding function of d-directional segment graphs
summary: To color a graph properly, one needs at least as many colors as the size of its biggest clique; therefore, the chromatic number χ is lower-bounded by the clique number ω. In general, there are no upper bounds on χ in terms of ω. The graphs for which we ...