jeu. 12 mars 2020 -- Laurent Perron (Google)

summary: A travers une série d'exemples, je décrierai les applications de la recherche opérationnelle et de l'optimisation discrète à Google. Puis je me focaliserai sur l'apport récent des techniques des moteurs SAT (satisfiabilité) et les challenges et opportunités qui lui sont liées.

jeu. 17 octobre 2019 -- Yannis Manoussakis (University Paris South and CNRS)

summary: We consider problems in edge- or vertex colored graphs. As an example, the Web graph may be considered as a vertex-colored graph where the color of a vertex represents the content of the corresponding page (red for mathematics, yellow for physics, etc.). When the edges/vertices of graphs are ...

ven. 27 septembre 2019 -- Nathalie Aubrun (ENS lyon)

summary: The domino problem for a finitely generated group asks whether there exists an algorithm which takes as input a finite alphabet and finitely many Wang tiles, and decides whether there exists a tiling of the group by this set of tiles. I will survey known results and present the ...

mer. 04 mai 2016 -- Professor Mariusz Wozniak (Department of Discrete Mathematics, AGH University, Cracow, Poland)

Abstract : Let us consider a coloring \(f\) of edges in a simple graph \(G = (V, E)\). Such acoloring defines for each vertex \(x \in V\) the palette of colors, i.e., the multiset of colors of edges incident with \(x\), denoted by \(S(x)\). These palettes can be used to ...

mer. 04 mai 2016 -- Pr. Liying Kang (Department of Mathematics, Shanghai University, China)

ABSTRACT: A maximal clique of a graph is a clique not properly contained in any other clique. A \(k\)-clique coloring of a graph is an assignment of a \(k\) colors to the vertices of \(G\) such that no maximal clique with at least two vertices is monochromatic. The clique-chromatic ...

ven. 08 avril 2016 -- Chien-Chung Huang (Gothenburg)

Abstract: We consider the problem of computing a large stable matching in a bipartite graph G = (A\cup B, E) where each vertex u \in A\cup B ranks its neighbors in an order of preference, perhaps involving ties.

A matching M is said to be stable if there is ...

ven. 18 mars 2016 -- Nguyen Kim Thang (IBISC)

In the setting of prophet inequalities and secretary problem, one observes a sequence of random objects and is allowed to stop the sequence at any time, claiming a reward equal to the most recent observation. The objective is to maximize the reward while observing the objects in an online manner ...

ven. 11 mars 2016 -- Hugo Férée (Université de Lille)

L'analyse récursive est un domaine qui s'attache à comprendre la notion de calcul sur des ensembles non dénombrables comme les nombres réels ou les fonctions réelles par exemple. Il permet entre autres de définir une notion de complexité sur de tels ensembles, mais les classes de complexité associées ...

ven. 26 février 2016 -- Benjamin Hellouin (Universidad Andrés Bello (Santiago))

Simulating universal computation in a given system has multiple uses: characterising the power of a model of computation, demonstrating the impossibility to predict the long-term behaviour or the properties of a physical model, forcing the system to adopt a given, computationally complex behaviour... The technical details of these simulations, corresponding ...

ven. 19 février 2016 -- Matthias Függer (Max-Planck-Institut)

In this talk I would like to advocate the study of non-classical distributed systems whose computing nodes can perform only simple computations under highly restricted communication mechanisms and memory capabilities.

I will present two problems, we are currently working on, one from chip design and one from biology, showing that ...