CS Forum: Dennis Olivetti, Gran Sasso Science Institute (GSSI)

CS department's public guest lecture on 'Distributed subgraph detection'. The lecture is open to everyone free-of-charge.

Dennis Olivetti
GSSI, L’Aquila, Italy

Host: Prof Jukka Suomela
Time: 14:15 (coffee at 14:00)
Venue: T5, CS building

Distributed subgraph detection

Abstract

Distributed property testing in networks has been introduced by Brakerski and Patt-Shamir (2011), with the objective of detecting the presence of large dense sub-networks in a distributed manner. In distributed property testing, the goal is to design randomized algorithms whose aim is to distinguish between graphs satisfying a property, and graphs far from satisfying that property, in the standard CONGEST model for distributed network computing.

Recently, Censor-Hillel et al. (2016) have shown how to detect 3-cycles in a constant number of rounds. In a follow up work, Fraigniaud et al. (2016) have shown how to detect 4-cycles in a constant number of rounds as well. However, the techniques in these latter works were shown not to generalize to larger cycles C_k with k >= 5.

First, we show that for every k >= 3, there exists a distributed property testing algorithm for C_k-freeness, performing in a constant number of rounds. Its round-complexity is O(1/epsilon) where epsilon (0 < epsilon < 1) is the property testing parameter measuring the gap between legal and illegal instances. Our algorithm  provides a distributed implementation of a combinatorial technique due to Erdos et al. for sparsening the set of partial solutions kept by the nodes at each round.

Then, we show how to generalize the algorithm, providing a deterministic algorithm for detecting the presence of a subgraph isomorphic to T running in a constant number of rounds, for every tree T. As a corollary of our result, we get that, for every graph pattern H composed of an edge and a tree connected in an arbitrary manner, there exists a (randomized) distributed testing algorithm for H-freeness, performing in  a constant number of rounds. All previous results of the literature concerning testing H-freeness for classical patterns H such as cycles and cliques can be viewed as direct consequences of our result, while our algorithm enables testing more complex patterns.

Bio

I am a PhD student in Computer Science at Gran Sasso Science Institute, L’Aquila, Italy. Since February 2016 I am visiting Institut de Recherche en Informatique Fondamentale (IRIF) in Paris, where I am working with my supervisor Prof. Pierre Fraigniaud. I received my BSc and MSc at the University of Bologna, Italy. My interests are mainly in theoretical computer science, and more in particular in distributed computing.