Publication

Who Started This Rumor? Quantifying the Natural Differential Privacy of Gossip Protocols

Related publications (40)

Graph Chatbot

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.

Weighted Gossip: Distributed Averaging Using Non-Doubly Stochastic Matrices

Martin Vetterli, Patrick Thiran, Florence Bénézit

This paper presents a general class of gossip-based averaging algorithms, which are inspired from Uniform Gossip [1]. While Uniform Gossip works synchronously on complete graphs, weighted gossip algorithms allow asynchronous rounds and converge on any conn ...

IEEE2010

Graph-Constrained Group Testing

Amin Karbasi, Mahdi Cheraghchi Bashi Astaneh, Soheil Mohajerzefreh

Non-adaptive group testing involves grouping arbitrary subsets of

n

items into different pools and identifying defective items based on tests obtained for each pool. Motivated by applications in network tomography, sensor networks and infection propagati ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2010

A bipartite strengthening of the Crossing Lemma

János Pach

Let G = (V, E) be a graph with n vertices and m >= 4n edges drawn in the plane. The celebrated Crossing Lemma states that G has at least Omega(m(3)/n(2)) pairs of crossing edges; or equivalently, there is an edge that crosses Omega(m(2)/n(2)) other edges. ...

2010

Degree-constrained edge partitioning in graphs arising from discrete tomography

Dominique de Werra, Bernard Ries

Starting from the basic problem of reconstructing a 2-dimensional image given by its projections on two axes, one associates a model of edge coloring in a complete bipartite graph. The complexity of the case with k=3 colors is open. Variations and special ...

2009

Blockers and transversals

Dominique de Werra, Bernard Ries, Rico Zenklusen

Given an undirected graph G = (V, E) with matching number v(G), we define d-blockers as subsets of edges B such that nu((V, E \ B)) = d. ...

2009

Exact Solution of the Gauge Symmetric p-Spin Glass Model on a Complete Graph

Nicolas Macris, Satish Babu Korada

We consider a gauge symmetric version of the p-spin glass model on a complete graph. The gauge symmetry guarantees the absence of replica symmetry breaking and allows to fully use the interpolation scheme of Guerra to rigorously compute the free energy. In ...

2009

Using Three States for Binary Consensus on Complete Graphs

Etienne Perron, Dinkar Vasudevan, Milan Vojnovic

We consider the binary consensus problem where each node in the network initially observes one of two states and the goal for each node is to eventually decide which one of the two states was initially held by the majority of the nodes. Each node contacts ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2009

Polar cographs

Dominique de Werra, Tinaz Ekim

Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. A graph is (s, k)-polar if there exists a partition A, B of its vertex set such that A induces a complete s-partite grap ...

Elsevier2008

Variations of coloring problems related to scheduling and discrete tomography

Bernard Ries

The graph coloring problem is one of the most famous problems in graph theory and has a large range of applications. It consists in coloring the vertices of an undirected graph with a given number of colors such that two adjacent vertices get different col ...

EPFL2007

Polar cographs

Dominique de Werra, Tinaz Ekim

Polar graphs are a natural extension of some classes of graphs like bipartite graphs, split graphs and complements of bipartite graphs. A graph is (s,k)-polar if there exists a partition A,B of its vertex set such that A induces a complete s-partite graph ...

2005

Graph-Constrained Group Testing

Amin Karbasi, Mahdi Cheraghchi Bashi Astaneh, Soheil Mohajerzefreh

Non-adaptive group testing involves grouping arbitrary subsets of

n

items into different pools and identifying defective items based on tests obtained for each pool. Motivated by applications in network tomography, sensor networks and infection propagati ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2010