2 papers
cs.DC2020
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…
cs.DC2020
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…