BARC talk by Vincent Cohen-Addad

Tuesday, 8 October 2019, Vincent Cohen-Addad, permanent researcher at Sorbonne Université, Paris, will give a talk on "From Local to Global: Local Search Algorithms Beyond the Worst-Case Analysis".

Title:
From Local to Global: Local Search Algorithms Beyond the Worst-Case Analysis

Abstract:
A classic problem in data analysis consists in partitioning the vertices of a network in such a way that vertices in the same set are densely connected. In practice, the most popular approaches rely on local search algorithms; not only for the ease of implementation and the efficiency, but also because of the accuracy of these methods on many real-world graphs. For example, the Louvain algorithm -- a local search based algorithm -- has quickly become the method of choice for detecting communities in social networks, accumulating more than 8600 citations over the past 10 years.

However, explaining the success of these methods remains an open

problem: in the worst-case, their performances can be arbitrarily bad.

In this work, we study these local search heuristics and aim at explaining their success and identifying the mechanisms that make them successful through a classic model for social networks, the stochastic block model. We give the first theoretical evidence that Louvain finds the underlying natural partition of the network.

Bio

Vincent Viallat Cohen-Addad a permanent CNRS researcher at Sorbonne Université, in the Laboratoire d'Informatique de Paris-6 (LIP6). The focus of his research is the design of algorithms for clustering and network design problems, with an emphasis on problems arising in data analysis and machine learning contexts. His goal is to come up with efficient algorithms and understand the complexity of these problems. Furthermore Vincent has a strong interest in online optimization, learning theory, computational geometry and fixed-parameter and fined-grained complexity.

Currently Vincent is PI of the ANR JCJC project on the foundations of clustering algorithms (FOCAL) and has recently won the Best Paper Award at SoCG 2019 for the paper "Almost Tight Lower Bounds for Hard Cutting Problems in Embedded Graphs" with Éric Colin de Verdière, Daniel Marx, Arnaud de Mesmay.

As an alumni of BARC 2017 we look forward to welcoming Vincent back at BARC for his visit.