Concept
Graph coloring
Related publications (321)
Expanding computational biochemistry towards complex and non-natural compounds
In the beginning was the metabolism. The biochemical processes that make life possible transformed the soup of chemicals into the life on Earth we know today. Since then, living organisms have evolved, and life on Earth has become more complex. Living orga ...
EPFL2023Beyond 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 ...
Brookline2023Distributed Optimization with Byzantine Robustness Guarantees
As modern machine learning continues to achieve unprecedented benchmarks, the resource demands to train these advanced models grow drastically. This has led to a paradigm shift towards distributed training. However, the presence of adversariesâwhether ma ...
EPFL2023Metastability 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 ...
SPRINGER2023Graph-based approximate message passing iterations
Approximate message passing (AMP) algorithms have become an important element of high-dimensional statistical inference, mostly due to their adaptability and concentration properties, the state evolution (SE) equations. This is demonstrated by the growing ...
OXFORD UNIV PRESS2023Multi-robot task allocation for safe planning against stochastic hazard dynamics
Maryam Kamgarpour, Orcun Karaca
We address multi-robot safe mission planning in uncertain dynamic environments. This problem arises in several applications including safety-critical exploration, surveillance, and emergency rescue missions. Computation of a multi-robot optimal control pol ...
2023Privatized graph federated learning
Ali H. Sayed, Stefan Vlaski, Elsa Rizk
Federated learning is a semi-distributed algorithm, where a server communicates with multiple dispersed clients to learn a global model. The federated architecture is not robust and is sensitive to communication and computational overloads due to its one-m ...
SPRINGER2023Unambiguous DNFs and Alon-Saks-Seymour
Mika Tapani Göös, Siddhartha Jain
We exhibit an unambiguous k-DNF formula that requires CNF width (Omega) over tilde (k(2)), which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon-Saks-Seymour problem in graph theory (posed in 1991), which ...
IEEE COMPUTER SOC2022Distributed Graph Learning With Smooth Data Priors
Pascal Frossard, Mireille El Gheche, Isabela Cunha Maia Nobre
Graph learning is often a necessary step in processing or representing structured data, when the underlying graph is not given explicitly. Graph learning is generally performed centrally with a full knowledge of the graph signals, namely the data that live ...
IEEE2022SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generators
Nathanaël Perraudin, Andreas Loukas, Karolis Martinkus
We approach the graph generation problem from a spectral perspective by first generating the dominant parts of the graph Laplacian spectrum and then building a graph matching these eigenvalues and eigenvectors. Spectral conditioning allows for direct model ...
JMLR-JOURNAL MACHINE LEARNING RESEARCH2022