5 citations · 15 across the 23 of their papers we have counts for
4 papers · 2 filters
Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
Pedro Montealegre, Diego Ramírez-Romero, Iván Rapaport
We present compact distributed interactive proofs for the recognition of two important graph classes, well-studied in the context of centralized algorithms, namely complement reduc…
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…
Shared vs Private Randomness in Distributed Interactive Proofs
Pedro Montealegre, Diego Ramírez-Romero, Ivan Rapaport
In distributed interactive proofs, the nodes of a graph G interact with a powerful but untrustable prover who tries to convince them, in a small number of rounds and through short…
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)…