research
∙
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...
share
research
∙
02/22/2023
Pattern detection in ordered graphs
A popular way to define or characterize graph classes is via forbidden s...
research
∙
08/30/2022
Lower bound for constant-size local certification
Given a network property or a data structure, a local certification is a...
research
∙
03/16/2022
Short and local transformations between (Δ+1)-colorings
Recoloring a graph is about finding a sequence of proper colorings of th...
research
∙
02/12/2022
What can be certified compactly?
Local certification consists in assigning labels (called certificates) t...
research
∙
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...
research
∙
10/05/2021
Local certification of MSO properties for bounded treedepth graphs
The graph model checking problem consists in testing whether an input gr...
research
∙
09/13/2021
Distributed recoloring of interval and chordal graphs
One of the fundamental and most-studied algorithmic problems in distribu...
research
∙
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...
research
∙
11/16/2020
The Secretary Problem with Independent Sampling
In the secretary problem we are faced with an online sequence of element...
research
∙
07/16/2020
Local Certification of Graphs with Bounded Genus
Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for aut...
research
∙
05/12/2020
Compact Distributed Certification of Planar Graphs
Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the exist...
research
∙
01/22/2020
Bibliography of distributed approximation on structurally sparse graph classes
This document is an informal bibliography of the papers dealing with dis...
research
∙
10/28/2019
Introduction to local certification
Local certification is an concept that has been defined and studied rece...
research
∙
09/16/2019
Note on distributed certification of minimum spanning trees
A distributed proof (also known as local certification, or proof-labelin...
research
∙
05/21/2019
Silent MST approximation for tiny memory
In network distributed computing, minimum spanning tree (MST) is one of ...
research
∙
05/21/2019
Memory Lower Bounds for Self-Stabilization
In the context of self-stabilization, a silent algorithm guarantees that...
research
∙
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 ...
research
∙
12/14/2018
Graph classes and forbidden patterns on three vertices
This paper deals with graph classes characterization and recognition. A ...
research
∙
03/26/2018
Local verification of global proofs
In this work we study the cost of local and global proofs on distributed...
research
∙
03/08/2018