Concept
Graph power
Publications associées (9)
Beyond 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 ...
Brookline2023Data-driven and Safe Networked Control with Applications to Microgrids
Today, automatic control is integrated into a wide spectrum of real-world systems such as electrical grids and transportation networks. Many of these systems comprise numerous interconnected agents, perform safety-critical operations, or generate large amo ...
EPFL2022Distributed 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 ...
IEEE2022The Sketching Complexity of Graph and Hypergraph Counting
Mikhail Kapralov, John Michael Goddard Kallaugher
Subgraph counting is a fundamental primitive in graph processing, with applications in social network analysis (e.g., estimating the clustering coefficient of a graph), database processing and other areas. The space complexity of subgraph counting has been ...
IEEE COMPUTER SOC2018A Fast Hadamard Transform for Signals with Sub-linear Sparsity in the Transform Domain
Martin Vetterli, Robin Scheibler, Saeid Haghighatshoar
In this paper, we design a new iterative low-complexity algorithm for computing the Walsh-Hadamard transform (WHT) of an N dimensional signal with a K-sparse WHT. We suppose that N is a power of two and K = O(N^α), scales sub-linearly in N for some α ∈ (0, ...
Institute of Electrical and Electronics Engineers2015Navigating Central Path with Electrical Flows: from Flows to Matchings, and Back
We present an O(m^10/7) = O(m^1.43)-time algorithm for the maximum s-t flow and the minimum s-t cut problems in directed graphs with unit capacities. This is the first improvement over the sparse-graph case of the long-standing O(m min{m^1/2, n^2/3}) runni ...
IEEE2013Efficient graph planarization in sensor networks and local routing algorithm
In this paper, we propose an efficient planarization algorithm and a routing algorithm dedicated to Unit Disk Graphs whose nodes are localized using the Virtual Raw Anchor Coordinate system (VRAC). Our first algorithm computes a planar 2-spanner under ligh ...
Ieee2012Dynamical dimer correlations at bipartite and non-bipartite Rokhsar-Kivelson points
We determine the dynamical dimer correlation functions of quantum dimer models at the Rokhsar-Kivelson point on the bipartite square and cubic lattices and the non-bipartite triangular lattice. On the basis of an algorithmic idea by Henley, we simulate a s ...
2008Efficient erasure correcting codes
We introduce a simple erasure recovery algorithm for codes derived from cascades of sparse bipartite graphs and analyze the algorithm by analyzing a corresponding discrete-time random process. As a result, we obtain a simple criterion involving the fractio ...
Institute of Electrical and Electronics Engineers2001