Concept
Taux d'expansion (théorie des graphes)
Publications associées (79)
Metastability of the Potts Ferromagnet on Random Regular Graphs
We study the performance of Markov chains for the q-state ferromagnetic Potts model on random regular graphs. While the cases of the grid and the complete graph are by now well-understood, the case of random regular graphs has resisted a detailed analysis ...
SPRINGER2023Beyond Spectral Gap: The Role of the Topology in Decentralized Learning
Martin Jaggi, Thijs Vogels, Hadrien Hendrikx
In data-parallel optimization of machine learning models, workers collaborate to improve their estimates of the model: more accurate gradients allow them to use larger learning rates and optimize faster. In the decentralized setting, in which workers commu ...
Brookline2023Space-Efficient Representations of Graphs
With the increasing prevalence of massive datasets, it becomes important to design algorithmic techniques for dealing with scenarios where the input to be processed does not fit in the memory of a single machine. Many highly successful approaches have emer ...
EPFL2022Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes
Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...
IEEE COMPUTER SOC2022fGOT: Graph Distances Based on Filters and Optimal Transport
Pascal Frossard, Mireille El Gheche, Hermina Petric Maretic, Giovanni Chierchia
Graph comparison deals with identifying similarities and dissimilarities between graphs. A major obstacle is the unknown alignment of graphs, as well as the lack of accurate and inexpensive comparison metrics. In this work we introduce the filter graph dis ...
ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE2022How to Match in Modern Computational Settings
Buddhima Ruwanmini Gamlath Gamlath Ralalage
This thesis focuses on the maximum matching problem in modern computational settings where the algorithms have to make decisions with partial information.First, we consider two stochastic models called query-commit and price-of-information where the algori ...
EPFL2021Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is known to be solvable in n^{3-o(1)} time, and it is widely open whether it has an O(n^{3-ε}) time algorithm for ε > 0. To better understand APSP, one often strives to obtain subcubic t ...
Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021