Équipe-projet INRIA GANG

Équipe thématique Systèmes complexes, réseaux, calcul distribué

## Systèmes complexes

#### Jour, heure et lieu

#### Contact(s)

### Séances passées

#### Année 2019

Systèmes complexes

Mardi 26 mars 2019, 14 heures, 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.

Systèmes complexes

Mercredi 6 mars 2019, 11 heures, 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.

Systèmes complexes

Mardi 5 mars 2019, 14 heures, 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

Systèmes complexes

Mardi 19 février 2019, 11 heures, Salle 3052

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

Systèmes complexes

Mardi 22 janvier 2019, 14 heures, Salle 3052

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

#### Année 2018

Systèmes complexes

Mardi 23 octobre 2018, 14 heures, 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.

Systèmes complexes

Mardi 10 juillet 2018, 15 heures, 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.

Systèmes complexes

Jeudi 5 juillet 2018, 14 heures, Salle 3052

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

Systèmes complexes

Vendredi 4 mai 2018, 11 heures, Salle 3052

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

Systèmes complexes

Mercredi 2 mai 2018, 14 heures, 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.

Systèmes complexes

Jeudi 22 mars 2018, 14 heures, 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.

Systèmes complexes

Mardi 20 mars 2018, 14 heures, Salle 1007

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

Systèmes complexes

Mardi 13 février 2018, 14 heures, Salle 1007

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

Systèmes complexes

Mardi 16 janvier 2018, 14 heures, 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.

#### Année 2017

Systèmes complexes

Mardi 12 décembre 2017, 14 heures, 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

Systèmes complexes

Mardi 14 novembre 2017, 14 heures, Salle 3052

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

This is joint work with Rémi Varloot.

Systèmes complexes

Mardi 17 octobre 2017, 14 heures, Salle 3052

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

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