On the Complexity of Asynchronous Gossip

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic (in the number of processes) communication complexity in the worst case: given a system with n processes and at most f < n/3 failures, any solution t ...

This work examines the problem of learning a network graph from signals emitted by the network nodes, according to a diffusion model ruled by a Laplacian combination policy. The challenging regime of partial observability is considered, where signals are c ...

Universal quantum algorithms that prepare arbitrary n-qubit quantum states require O(2n) gate complexity. The complexity can be reduced by considering specific families of quantum states depending on the task at hand. In particular, multipartite quantum st ...

Two prominent categories for achieving coordinated multirobot displacement are flocking and navigation in formation. Both categories have their own body of literature and characteristics, including their respective advantages and disadvantages. While typic ...

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 ...

In this thesis we propose and analyze algorithms for some numerical linear algebra tasks: finding low-rank approximations of matrices, computing matrix functions, and estimating the trace of matrices. In the first part, we consider algorithms for building ...

The complexity of many-body quantum wave functions is a central aspect of several fields of physics and chemistry where nonperturbative interactions are prominent. Artificial neural networks (ANNs) have proven to be a flexible tool to approximate quantum m ...

This paper reports on the computation of a discrete logarithm in the finite field F-230750, breaking by a large margin the previous record, which was set in January 2014 by a computation in F-29234. The present computation made essential use of the elimina ...

Background Significant efforts have been made in building large-scale kinetic models of cellular metabolism in the past two decades. However, most kinetic models published to date, remain focused around central carbon pathways or are built around ad hoc re ...

Centralized and cloud computing-based network architectures are the promising tracks of future communication systems where a large scale compute power can be virtualized for various algorithms. These architectures rely on high-performance communication lin ...

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut (MAXCUT) in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communica ...

This paper examines the binning of two types of parts with random characteristics, so that a componentwise monotonic evaluation criterion exhibits a minimum deviation to a given target value over all possible realizations. The optimal matching classes are ...

Deep neural networks have been empirically successful in a variety of tasks, however their theoretical understanding is still poor. In particular, modern deep neural networks have many more parameters than training data. Thus, in principle they should over ...

This paper introduces a new algorithm for consensus optimization in a multi-agent network, where all agents collaboratively find a minimizer for the sum of their private functions. All decentralized algorithms rely on communications between adjacent nodes. ...

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communication and ...

In this thesis we give new algorithms for two fundamental graph problems. We develop novel ways of using linear programming formulations, even exponential-sized ones, to extract structure from problem instances and to guide algorithms in making progress. S ...

Options are some of the most traded financial instruments and computing their price is a central task in financial mathematics and in practice. Consequently, the development of numerical algorithms for pricing options is an active field of research. In gen ...

Remote Direct Memory Access (RDMA) is becoming widely available in data centers. This technology allows a process to directly read and write the memory of a remote host, with a mechanism to control access permissions. In this paper, we study the fundamenta ...

The online matching problem was introduced by Karp, Vazirani and Vazirani nearly three decades ago. In that seminal work, they studied this problem in bipartite graphs with vertices arriving only on one side, and presented optimal deterministic and randomi ...

It was previously shown that the problem of verifying whether a finite concurrent system is linearizable can be done with an EXPSPACE complexity. However, the best known lower bound is PSPACE-hardness, and can be obtained using a reduction from control-sta ...

On the Complexity of Asynchronous Gossip

Chat with Graph Search

Byzantine consensus is Θ(n^2): the Dolev-Reischuk bound is tight even in partial synchrony!

Learning Dynamic Graphs under Partial Observability

Efficient Preparation of Cyclic Quantum States

Hybrid Flock - Formation Control Algorithms

Data-driven and Safe Networked Control with Applications to Microgrids

Fast deterministic and randomized algorithms for low-rank approximation, matrix functions, and trace estimation

Variational Monte Carlo Calculations of A

Computation Of A 30750-Bit Binary Field Discrete Logarithm

The effects of model complexity and size on metabolic flux distribution and control: case study in Escherichia coli

Modified Joint Channel-and-Data Estimation for One-Bit Massive MIMO

Local approximation of the Maximum Cut in regular graphs

Minimum-Error Classes for Matching Parts

On Vacuous and Non-Vacuous Generalization Bounds for Deep Neural Networks

Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization

Local Approximation of the Maximum Cut in Regular Graphs

New Graph Algorithms via Polyhedral Techniques

Numerical methods for option pricing: polynomial approximation and high dimensionality

The Impact of RDMA on Agreement

Online Matching with General Arrivals

On the complexity of linearizability