Thematic team Complex systems, networks, and distributed computing

INRIA project-team GANG

## Complex systems

#### Day, hour and place

Tuesday at 2pm, room 1007

The calendar of events (iCal format).

In order to add the event calendar to your favorite agenda, subscribe to the calendar by given this link

#### Contact(s)

### Previous talks

#### Year 2020

Complex systems

Thursday June 4, 2020, 2PM, Online

**Mikaël Rabie** (LIP6, Sorbonne Université) *Lower bounds for maximal matchings and maximal independent sets*

#### Year 2019

Complex systems

Monday June 24, 2019, 11AM, Salle 3052

**Carola Doerr** (CNRS, LIP6 Sorbonne University) *Evolutionary Algorithms – From Theory to Practice and Back*

In the last 15 years, the theory of randomized black-box optimization has advanced considerably, and has contributed to efficient optimization by providing insights into the working principles of black-box optimization which are hard or impossible to obtain by empirical means. On the other hand, empirically-guided benchmarking has opened up new research directions for theoretical investigations.

In this presentation we will discuss the state of the art in the theory of randomized black-box optimization algorithms. As part of this critical survey we will also mention a number of open questions and connections to other fields of Computer Science.

Complex systems

Tuesday March 26, 2019, 2PM, Salle 3052

**Anaïs Durand** (LIP6, Sorbonne Université) *Contention-related crash failures*

In this talk, I will present k-set agreement and renaming algorithms that are resilient to two types of process crash failures: “λ-constrained” crash failures (as previously defined) and classical crash failures.

Complex systems

Wednesday March 6, 2019, 11AM, Salle 3052

**Marc Lelarge** (Inria & ENS Paris) *Spectral embedding for graph classification*

Although our SGE is handcrafted, we also show how our generic embedding technique can be learned and built in a data-driven manner opening the way to new learning algorithms and deep learning architectures with some invariant constraints built-in.

Complex systems

Tuesday March 5, 2019, 2PM, Salle 3052

**Mikaël Rabie** (IRIF) *Distributed Reconfiguration of Graph Problems*

For example, a recoloration problem asks if we can go from a coloration to another, by changing the color of a node at each transition (with the coloring still valid in the intermediate steps).

In this talk, the goal is to consider distributed version of two reconfiguration problems: recoloring, and reconfiguring independent sets. To parallelise the process, we will accept to change the state of different nodes at once, under certain hypothesis (for example, we will recolor an independent set of nodes). The questions will be, using the LOCAL model, how much communication is needed (i.e. how much a node needs knowledge of its neighborhood) in order to produce a reconfiguration schedule of a given length.

For the distributed recoloring, we prove that the addition of colors for the intermediate steps is needed for some cases in order to have a solution. I will provide the analysis of trees and toroidal grids, where we want to go from a 3-coloring to another with the use of a 4th color. In the case of trees, a constant schedule can be found after O(log n) communications. In the case of grids, a linear number of communications is necessary.

For the reconfiguration of independent sets, we will present different transitions from the centralized settings, to then justify the one we use. We prove that a constant schedule can be found after O(log*n) communications, and a linear schedule can be found after a constant number of communications.

Those works are the result of collaborations with Marthe Bonamy, Keren Censor-Hillel, Paul Ouvrard, Jara Uitto and Jukka Suomela

Complex systems

Tuesday February 19, 2019, 11AM, Salle 3052

**Danupon Nanongkai** (KTH) *Distributed Shortest Paths, Exactly*

Complex systems

Tuesday January 22, 2019, 2PM, Salle 3052

**Guillaume Ducoffe** (ICI Roumanie) *Computing Giant Diameters with Breadth-First Search and Range Queries*

#### Year 2018

Complex systems

Tuesday October 23, 2018, 2PM, Salle 3052

**Yllka Velaj** (CWI Amsterdam) *Stable Outcomes in Modified Fractional Hedonic Games*

We are interested in the scenario in which agents, individually or jointly, choose to form a new coalition or to join an existing one, until a stable outcome is reached. To this aim, we consider common stability notions, leading to strong Nash stable outcomes, Nash stable outcomes or core stable outcomes: we study their existence, complexity and performance, both in the case of general weights and in the case of 0-1 weights.

Complex systems

Tuesday July 10, 2018, 3PM, Salle 3052

**Nicolas K. Blanchard** (IRIF) *Human-Computable Passwords*

Following in the footsteps of Manuel Blum et al. we recently proposed a humanly-computable password scheme called Cue-Pin-Select. It can generate (and regenerate) passwords on the go using only the user's brain for computation. It has the advantage of creating nigh-unforgettable passwords, not requiring any external storage or computing device, and can be executed in less than a minute to create a new password (potentially down to 30s with a bit of training). All passwords generated are 52-bit secure and can maintain 40+ bit security even against adversaries in possession of a stolen password

This talk will summarize work done in the past 6 months with Ted Selker and doesn't require any prior knowledge. It will start with the Cue-Pin-Select algorithm, cover an improvement we found that applies to all passphrase-based security systems, and explain some of the work currently being done to have better tools to study password schemes and human computation.

The talk will be given in English unless the audience is entirely composed of French-speakers.

Complex systems

Thursday July 5, 2018, 2PM, Salle 3052

**Laurent Viennot** (Inria Paris et IRIF) *Introduction to the blockchain*

Complex systems

Friday May 4, 2018, 11AM, Salle 3052

**Emanuele Natale** (Max-Planck-Institut für Informatik) *Pooling or Sampling: Collective Dynamics for Electrical Flow Estimation*

Complex systems

Wednesday May 2, 2018, 2PM, Salle 3052

**Mauro Sozio** (Telecom Paristech) *Fully Dynamic k-center Clustering and Graph Partitioning*

We develop a (2+epsilon)-approximation algorithm for the k-center clustering problem with “small” amortized cost under the fully dynamic adversarial model. In such a model, points can be added or removed arbitrarily, provided that the adversary does not have access to the random choices of our algorithm. The amortized cost of our algorithm is poly-logarithmic when the ratio between the maximum and minimum distance between any two points in input is bounded by a polynomial, while k and epsilon are constant. Our theoretical results are complemented with an extensive experimental evaluation on dynamic data from Twitter, Flickr, as well as trajectory data, demonstrating the effectiveness of our approach. We conclude our talk with some interesting directions for future work. In particular, we are going to discuss the challenges in developing a fully dynamic algorithm for graph partitioning.

Seminaire du Pole

Complex systems

Thursday March 22, 2018, 2PM, Salle 3052

**Przemyslaw Uznanski** (ETH Zurich) *Searching in the presence of errors, revisited*

In graph searching with vertex queries, whenever Questioner queries a vertex $v$, Responder answers with neighbor $w$ of $v$ that lies on the shortest path from $v$ to target or with $v$ itself (as introduced by Emamjomeh-Zadeh et al. [STOC 2016]). We show that a simple strategy of querying weighted-1-median vertex and multiplicatively updating weights of vertices leads to $O(\log n + L)$ queries with fixed $L$ lies, generalizing results of Emamjomeh-Zadeh et al. By careful selection of potential this leads to $O(\log n / \varepsilon^2)$ queries when number of lies is bounded linearly by ratio $r = 1/2-\varepsilon$, or are subject to errors with probability $p = 1/2-\varepsilon$ (in that case target is located correctly w.h.p.). This improves result of Emamjomeh-Zadeh et al. for some selection of parameters (locating w.h.p. when $\varepsilon = \Omega(1/\sqrt{\log n})$, and generalizes their result to other error models.

We introduce an edge queries model, in which, whenever Questioner queries an edge $e$, Responder answers with endpoint of $e$ that is not further to target. We show that appropriately defining weighted-1-median edge leads to $O(\Delta(\log n + L))$ length strategy in graphs of max degree $\Delta$, which leads to $O(\Delta \log n / \varepsilon^2)$ queries when lies are bounded linearly with rate $r = \frac{1}{\Delta+1}(1-\varepsilon)$ and $O(\Delta \log^2 n/\varepsilon^2)$ with error probability $p = 1/2-\varepsilon$.

Our results for edge queries almost automatically apply to comparison based search of integer ranges, simplifying and improving many existing results. We also note that vertex based queries translate to (not considered previously to our knowledge) ternary comparisons, and this shows a separation between power of binary and ternary comparisons in the linearly bounded lies (Questioner can find target iff $r < \frac13$ for former case, $r < \frac12$ for latter case).

Tweaking initial distribution of potentials, our results apply to searching in unbounded integer domains as well, leading to both simplification and significant improvement in length of strategies, and providing first results for many combinations of query model and error model.

Complex systems

Tuesday March 20, 2018, 2PM, Salle 1007

**Pierluigi Crescenzi** (Universite de Pise) *Computing node centrality in large graphs: from theory to practice and back*

Complex systems

Tuesday February 13, 2018, 2PM, Salle 1007

**Nicolas Behr** (ENS) *Combinatorics of stochastic rewriting systems*

Complex systems

Tuesday January 16, 2018, 2PM, Salle 3014

**Nicolas Thiery** (Université Paris Sud) *Computing huge subspaces of diagonal harmonic polynomials: symmetries to the rescue!*

To fuel his ongoing studies François needed to compute the structure of H(5,6). This is a space of dimension 6.10^5 made of polynomials in 30 variables of degree up to 15, each having thousands of terms.

In this talk, I'll explain how the calculation can now be completed in 45 minutes with a dozen cores and ~15Go of memory. This exploits a combination of strategies (symmetries, representation theory of the symmetric and general linear group, …), each of which reduces the complexity in time and memory by one or two orders of magnitude.

There will be little prerequisites and it's my hope that some strategies (and maybe the code!) could be used in other contexts.

#### Year 2017

Complex systems

Tuesday December 12, 2017, 2PM, Salle 3052

**Jean Krivine** (IRIF) *Incremental Update for Graph Rewriting*

Reference: Boutillier P., Ehrhard T., Krivine J. (2017) Incremental Update for Graph Rewriting. In: Yang H. (eds) Programming Languages and Systems. ESOP 2017. Lecture Notes in Computer Science, vol 10201. Springer, Berlin, Heidelberg

Complex systems

Tuesday November 14, 2017, 2PM, Salle 3052

**Laurent Massoulié** (MSR-Inria) *Rapid Mixing of Local Graph Dynamics*

This is joint work with Rémi Varloot.

Séminaire de Pôle

Complex systems

Tuesday October 17, 2017, 2PM, Salle 3052

**Claire Mathieu** (DI - ENS) *Online k-compaction*

This is joint work with Carl Staelin, Neal E. Young, and Arman Yousefi.