Category: seminars
Canadian Traveller Problems in Temporal Graphs.
summary: We focus on the Canadian Traveller Problem, where a traveller aims to travel on a network from s to t with the minimum cost, considering that a maximum of k edges can be blocked. These edges remain hidden from the traveller until they visit one of their endpoints. We ...
Current trends in Optimal Stopping Problems and Machine Learning
summary: Stochastic optimal stopping problems have a wide range of applications, from finance and economics to neuroscience,
robotics, and energy management. Many real-world applications involve complex models that have driven the development of
sophisticated numerical methods.
Recently, computational methods based on machine learning methods have been developed for solving such ...
Transversals in a collection of graphs with degree conditions
summary: Let G={G_1, G_2, ... , G_m} be a collection of n-vertex graphs on the same vertex set V (a graph system), and F be a simple graph with e(F) ≤ m. If there is an injection f: E(F) → [m] such that e &isinv E(G_{f(e)}) for each ...
Compact local certification of MSO properties for several tree-like parameters
summary: Local certification is interested in assigning labels (called certificates) to the vertices of a graph, in order to certify a certain property about said graph, or the correctness of a data-structure distributed on the graph. For the verification to be local, a vertex may only "see" its neighbourhood. A ...
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 ...
Polynômes de Jack et constellations b-déformées
La série génératrice des cartes orientables pondérées (et sa généralisation aux constellations) peut s’exprimer simplement à l’aide des fonctions de Schur. La série des cartes non-orientées (c’est à dire orientable ou non) admet une expression similaire où les fonctions de Schur sont remplacées par les polynomes zonaux ...
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 ...