Tag: networks
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 ...
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 ...
Proper vertex coloring with odd occurrence - Probabilistic approach
summary: In graph theory, a graph coloring is an assignment of colors to elements of a graph subject to certain constraints. A vertex coloring is said to be proper if any pair of two adjacent vertices are assigned distinct colors. For a graph G, the chromatic number χ(G) is ...
Some results on directed coloring
summary: Proper coloring of undirected graphs lies among the most studied
problems in graph theory. It asks to color vertices while giving
different colors to adjacent ones.
In 1982, Neumann-Lara introduced a generalization of this problem to
directed graphs. When walking in an undirected graph, an undirected edge
between two ...
Density of sphere packings: from coins to oranges
summary: How to stack an infinite number of oranges to maximize the proportion of the covered space? Kepler conjectured that the "cannonball" packing is an optimal way to do it. This conjecture took almost 400 years to prove and the proof of Hales and Ferguson consists of 6 papers and ...
An introduction to twin-width in graphs via the study of highly inapproximable problems
summary: The goal of this seminar is to introduce the graph parameter "twin-width", defined by Bonnet et al. in 2020. The collection of graphs with bounded twin-width generalizes many well-known families of graphs : planar, bounded treewidth and cliquewidth, unit interval,... The first motivation behind this parameter was that FO-expressible NP-hard ...
TracInAD: Measuring Influence for Anomaly Detection
summary: As with many other tasks, neural networks prove very effective for anomaly detection purposes. However, very few deep-learning models are suited for detecting anomalies on tabular datasets. This talk proposes a novel methodology to flag anomalies based on TracIn, an influence measure initially introduced for explicability purposes. The proposed ...
Introduction à l'apprentissage par renforcement
summary: Cet exposé proposera une introduction à l'apprentissage par renfocement, en présentant les fonctions à maximiser et les types d'approches employées. La présentation suivra l'évolution historique du domaine, du Q-Learning au Deep Reinforcement Learning, en passant par des travaux étant devenus populaires tel que AlphaGo. Nous conclurons ...
Optimal curing policy for epidemic spreading over a community network with heterogeneous population
summary: The design of an efficient curing policy, able to stem an epidemic process at an affordable cost, has to account for the structure of the population contact network supporting the contagious process. Thus, we tackle the problem of allocating recovery resources among the population, at the lowest cost possible ...
Economics of Age of Information (AoI) Management: Pricing and Competition
Summary: Fueled by the rapid development of communication networks and sensors in portable devices, today many mobile users are invited by content providers to sense and send back real-time useful information (e.g., traffic observations and sensor data) to keep the freshness of the online platforms’ content updates. However, due ...