Laurent Feuilloley | DeepAI

DeepAI AI Chat

Featured Co-authors

Vincent Cohen-Addad
45 publications
Nicolas Bousquet
43 publications
Guillaume Ducoffe
22 publications
Ami Paz
20 publications
Pierre Fraigniaud
18 publications
Théo Pierron
17 publications
Pedro Montealegre
17 publications
Tatiana Starikovskaya
14 publications
Juho Hirvonen
14 publications
Marc Heinrich
14 publications
Mikaël Rabie
12 publications

∙ 04/12/2023

When Should You Wait Before Updating? Toward a Robustness Refinement

Consider a dynamic network and a given distributed problem. At any point...

0 Swan Dubois, et al. ∙

∙ 02/22/2023

Pattern detection in ordered graphs

A popular way to define or characterize graph classes is via forbidden s...

0 Guillaume Ducoffe, et al. ∙

∙ 08/30/2022

Lower bound for constant-size local certification

Given a network property or a data structure, a local certification is a...

0 Virgina Ardévol Martínez, et al. ∙

∙ 03/16/2022

Short and local transformations between (Δ+1)-colorings

Recoloring a graph is about finding a sequence of proper colorings of th...

0 Nicolas Bousquet, et al. ∙

∙ 02/12/2022

What can be certified compactly?

Local certification consists in assigning labels (called certificates) t...

0 Nicolas Bousquet, et al. ∙

∙ 12/01/2021

Classifying grounded intersection graphs via ordered forbidden patterns

It was noted already in the 90s that many classic graph classes, such as...

0 Laurent Feuilloley, et al. ∙

∙ 10/05/2021

Local certification of MSO properties for bounded treedepth graphs

The graph model checking problem consists in testing whether an input gr...

0 Nicolas Bousquet, et al. ∙

∙ 09/13/2021

Distributed recoloring of interval and chordal graphs

One of the fundamental and most-studied algorithmic problems in distribu...

0 Nicolas Bousquet, et al. ∙

∙ 07/30/2021

Local certification of graph decompositions and applications to minor-free classes

Local certification consists in assigning labels to the nodes of a netwo...

0 Nicolas Bousquet, et al. ∙

∙ 11/16/2020

The Secretary Problem with Independent Sampling

In the secretary problem we are faced with an online sequence of element...

0 Jose Correa, et al. ∙

∙ 07/16/2020

Local Certification of Graphs with Bounded Genus

Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for aut...

0 Laurent Feuilloley, et al. ∙

∙ 05/12/2020

Compact Distributed Certification of Planar Graphs

Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the exist...

0 Laurent Feuilloley, et al. ∙

∙ 01/22/2020

Bibliography of distributed approximation on structurally sparse graph classes

This document is an informal bibliography of the papers dealing with dis...

0 Laurent Feuilloley, et al. ∙

∙ 10/28/2019

Introduction to local certification

Local certification is an concept that has been defined and studied rece...

0 Laurent Feuilloley, et al. ∙

∙ 09/16/2019

Note on distributed certification of minimum spanning trees

A distributed proof (also known as local certification, or proof-labelin...

0 Laurent Feuilloley, et al. ∙

∙ 05/21/2019

Silent MST approximation for tiny memory

In network distributed computing, minimum spanning tree (MST) is one of ...

0 Lélia Blin, et al. ∙

∙ 05/21/2019

Memory Lower Bounds for Self-Stabilization

In the context of self-stabilization, a silent algorithm guarantees that...

0 Lélia Blin, et al. ∙

∙ 12/21/2018

Lower bounds for text indexing with mismatches and differences

In this paper we study lower bounds for the fundamental problem of text ...

0 Vincent Cohen-Addad, et al. ∙

∙ 12/14/2018

Graph classes and forbidden patterns on three vertices

This paper deals with graph classes characterization and recognition. A ...

0 Laurent Feuilloley, et al. ∙

∙ 03/26/2018

Local verification of global proofs

In this work we study the cost of local and global proofs on distributed...

0 Laurent Feuilloley, et al. ∙

∙ 03/08/2018

Redundancy in Distributed Proofs

Distributed proofs are mechanisms enabling the nodes of a network to col...

0 Laurent Feuilloley, et al. ∙