Category: seminars
Auction mechanisms for allocation and pricing in Edge Computing
summary: Soon, billions of devices will be connected to the Internet, and most of them will need external resources to store and process their data. Edge Computing can benefit these devices by making these resources available at the network's edges to be closer to the user. However, these offered ...
A Closure Lemma for tough graphs and Hamiltonian degree conditions
summary: A graph G is Hamiltonian if there exists a cycle in G containing all vertices of G exactly once. A graph G is t-tough if, for all subsets of vertices S, the number of connected components in G−S is at most |S|/t. We extended the theorem of ...
Memory-Optimization for Self-Stabilizing Distributed Algorithms
summary: Self-stabilization is a suitable paradigm for distributed systems, particularly prone to transient faults. Errors such as memory or messages corruption, break of a communication link, can put the system in an inconsistent state. A protocol is self-stabilizing if, whatever the initial state of the system, it guarantees that it ...
Algorithmes de partitionnement par comparaison de paires
On cherche à reconstruire une partition d'un ensemble donné en envoyant des paires d'éléments à un oracle qui nous indique s'ils appartiennent à la même partie de la partition. Nous cherchons les algorithmes qui retrouvent la partition en un minimum de questions à l'oracle. Ce problème ...
Algorithms for the Metric Dimension problem on directed graphs
summary: In graph theory, the Metric Dimension problem is the following: we are looking for a minimum-size set R of vertices, such that for any pair of vertices of the graph, there is a vertex from R whose two distances to the vertices of the pair are distinct. This problem ...
Complexity of positional games
summary: Positional 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 ...
Language-theoretic methods in semigroup theory
Language-theoretic methods in combinatorial group theory go back to the fundamental work by Anisimov in the 1970s. Since then, the area has exploded, including such deep theorems as the Muller-Schupp theorem: a group has context-free word problem if and only if it is virtually free. In this talk, I will ...
The Domino Snake Problem
summary: Deep within the swamp of undecidability lies the elusive domino snake. This species, first discovered in the 1970s by Myers, was originally introduced as an a priori simpler problem than the now celebrated Domino Problem. In this talk we will take a tour through what is known about this ...
The fixed-point construction in tilings
summary: Consider a tileset, i.e. a finite set of colors along with some adjacency constraints between them. It defines the set of colorings of the infinite grid that respects these adjacency constraints. Such a coloring is called a tiling. Given a tileset as input, a question naturally arises: does ...
Lattice properties of acyclic pipe dreams
summary: Pipe dreams were introduced by Bergeron and Billey in order to study Schubert polynomials and encode the algebraic structure of the symmetric group. In particular, with well-chosen parameters, they have the combinatorial structure of the Tamari lattice, a well-known quotient of the weak order on permutations. In this presentation ...