Title: Distributed Computing and Large Graph Mining

Lecturer: Pierre Fraignaud, IRIF Université Paris Diderot – Paris 7 e PierLuigi Crescenzi

Period: 

April 26: 15-17 Sala Riunioni Ovest

April 27: 9-11 Sala Seminari Ovest

April 28: 9-11 TBA

May 2, 3, 4, 5: 9-11 Sala Seminari Ovest

Distributed computing is a field of computer science that studies distributed systems, i.e., systems in which  a collection of autonomous computing entities coordinate their actions via some communication medium. The objective of the first part of this course is to introduce the main techniques of algorithm design and analysis for distributed computing, enabling the computing entities aiming at collectively solve a common task. This part of the course will focus on the main computing models, capturing different aspects of distributed computing, including network computing, asynchrony, fault-tolerance, etc. For each model, the course will present the main techniques for (deterministic and probabilistic) algorithm design, and for deriving lower bounds and impossibility results.

In the second part of the course, we will take a graph mining roundtrip, from theory to practice and back. In particular, we will focus on the computation of several graph topological measures, for which polynomial-time algorithms are available that in "practice" are not useful, due to the huge size of the networks to be analysed. Switching to "theory", we will show that, unfortunately, for these measures no best algorithm exists (under reasonable complexity theory assumptions). This will lead us back to "practice": we will describe heuristics that, in the case of real-world graphs, allow us to compute these measures in linear time. These results will finally motivate our return to "theory" in order to understand the reason why, in practice, these heuristics work so well.