research
∙
09/09/2023
Local Certification of Some Geometric Intersection Graph Classes
In the context of distributed certification, the recognition of graph cl...
share
research
∙
07/26/2023
Distributed Certification for Classes of Dense Graphs
A proof-labeling scheme (PLS) for a boolean predicate Π on labeled graph...
research
∙
01/27/2023
Energy-Efficient Distributed Algorithms for Synchronous Networks
We study the design of energy-efficient algorithms for the LOCAL and CON...
research
∙
08/04/2022
Computing Power of Hybrid Models in Synchronous Networks
During the last two decades, a small set of distributed computing models...
research
∙
12/06/2021
Distributed Interactive Proofs for the Recognition of Some Geometric Intersection Graph Classes
A graph G=(V,E) is a geometric intersection graph if every node v ∈ V is...
research
∙
12/06/2021
A Meta-Theorem for Distributed Certification
Distributed certification, whether it be proof-labeling schemes, locally...
research
∙
12/06/2020
Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
We present compact distributed interactive proofs for the recognition of...
research
∙
07/16/2020
Local Certification of Graphs with Bounded Genus
Naor, Parter, and Yogev [SODA 2020] recently designed a compiler for aut...
research
∙
06/29/2020
Shared vs Private Randomness in Distributed Interactive Proofs
In distributed interactive proofs, the nodes of a graph G interact with ...
research
∙
05/12/2020