32 citations · 76 across the 27 of their papers we have counts for
34 papers
The local complexity of certifying parity
Nicolas Bousquet, Laurent Feuilloley, Jorge Valenzuela +1
In this paper, we consider the problem of locally certifying that the size of a network is even, or more generally, congruent to some fixed number. The parity property is one of th…
Polynomial Time Local Decision Revisited
Laurent Feuilloley, Soumyadeep Paul, Ami Paz
We consider three classification systems for distributed decision tasks: With unbounded computation and certificates, defined by Balliu, D'Angelo, Fraigniaud, and Olivetti [JCSS'18…
Decreasing verification radius in local certification
Laurent Feuilloley, Jan Janoušek, Jan Matyáš Křišťan +1
This paper deals with local certification, specifically locally checkable proofs: given a graph property, the task is to certify whether a graph satisfies the property. The verific…
Global certification via perfect hashing
Nicolas Bousquet, Laurent Feuilloley, Sébastien Zeitoun
In this work, we provide an upper bound for global certification of graph homomorphism, a generalization of graph coloring. In certification, the nodes of a network should decide i…
Local certification of forbidden subgraphs
Nicolas Bousquet, Linda Cook, Laurent Feuilloley +2
Detecting specific structures in a network has been a very active theme of research in distributed computing for at least a decade. In this paper, we start the study of subgraph de…
Local certification of local properties: tight bounds, trade-offs and new parameters
Nicolas Bousquet, Laurent Feuilloley, Sébastien Zeitoun
Local certification is a distributed mechanism enabling the nodes of a network to check the correctness of the current configuration, thanks to small pieces of information called c…
When Should You Wait Before Updating? Toward a Robustness Refinement
Swan Dubois, Laurent Feuilloley, Franck Petit +1
Consider a dynamic network and a given distributed problem. At any point in time, there might exist several solutions that are equally good with respect to the problem specificatio…
Pattern detection in ordered graphs
Guillaume Ducoffe, Laurent Feuilloley, Michel Habib +1
A popular way to define or characterize graph classes is via forbidden subgraphs or forbidden minors. These characterizations play a key role in graph theory, but they rarely lead…
Lower bound for constant-size local certification
Virgina Ardévol Martínez, Marco Caoduro, Laurent Feuilloley +3
Given a network property or a data structure, a local certification is a labeling that allows to efficiently check that the property is satisfied, or that the structure is correct.…
Short and local transformations between ()-colorings
Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich +1
Recoloring a graph is about finding a sequence of proper colorings of this graph from an initial coloring to a target coloring . Adding the constraint that each pair of cons…
What can be certified compactly?
Nicolas Bousquet, Laurent Feuilloley, Théo Pierron
Local certification consists in assigning labels (called \emph{certificates}) to the nodes of a network to certify a property of the network or the correctness of a data structure…
Classifying grounded intersection graphs via ordered forbidden patterns
Laurent Feuilloley, Michel Habib
It was noted already in the 90s that many classic graph classes, such as interval, chordal, and bipartite graphs, can be characterized by the existence of an ordering of the vertic…
Local certification of MSO properties for bounded treedepth graphs
Nicolas Bousquet, Laurent Feuilloley, Théo Pierron
The graph model checking problem consists in testing whether an input graph satisfies a given logical formula. In this paper, we study this problem in a distributed setting, namely…
Distributed recoloring of interval and chordal graphs
Nicolas Bousquet, Laurent Feuilloley, Marc Heinrich +1
One of the fundamental and most-studied algorithmic problems in distributed computing on networks is graph coloring, both in bounded-degree and in general graphs. Recently, the stu…
Local certification of graph decompositions and applications to minor-free classes
Nicolas Bousquet, Laurent Feuilloley, Théo Pierron
Local certification consists in assigning labels to the nodes of a network to certify that some given property is satisfied, in such a way that the labels can be checked locally. I…
The Secretary Problem with Independent Sampling
José Correa, Andrés Cristi, Laurent Feuilloley +2
In the secretary problem we are faced with an online sequence of elements with values. Upon seeing an element we have to make an irrevocable take-it-or-leave-it decision. The goal…
Local Certification of Graphs with Bounded Genus
Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre +3
Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for automatically translating standard centralized interactive protocols to distributed interactive protocols, as i…
Compact Distributed Certification of Planar Graphs
Laurent Feuilloley, Pierre Fraigniaud, Ivan Rapaport +3
Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the existence of a \emph{distributed interactive proof} for planarity (i.e., for certifying that a network is planar)…
Bibliography of distributed approximation beyond bounded degree
Laurent Feuilloley
This document is an informal bibliography of the papers dealing with distributed approximation algorithms. A classic setting for such algorithms is bounded degree graphs, but there…
Introduction to local certification
Laurent Feuilloley
A distributed graph algorithm is basically an algorithm where every node of a graph can look at its neighborhood at some distance in the graph and chose its output. As distributed…
Note on distributed certification of minimum spanning trees
Laurent Feuilloley
A distributed proof (also known as local certification, or proof-labeling scheme) is a mechanism to certify that the solution to a graph problem is correct. It takes the form of an…
Silent MST approximation for tiny memory
Lélia Blin, Swan Dubois, Laurent Feuilloley
In this paper we show that approximation can help reduce the space used for self-stabilization. In the classic \emph{state model}, where the nodes of a network communicate by readi…
Optimal Space Lower Bound for Deterministic Self-Stabilizing Leader Election Algorithms
Lélia Blin, Laurent Feuilloley, Gabriel Le Bouder
Given a boolean predicate on labeled networks (e.g., proper coloring, leader election, etc.), a self-stabilizing algorithm for is a distributed algorithm that can start fro…
Lower bounds for text indexing with mismatches and differences
Vincent Cohen-Addad, Laurent Feuilloley, Tatiana Starikovskaya
In this paper we study lower bounds for the fundamental problem of text indexing with mismatches and differences. In this problem we are given a long string of length , the "tex…