Fiche du document
3 août 2020
- handle: 10670/1.6al8zg
- halshs: halshs-02991868
- doi: 10.1145/3382734.3404505
Ce document est lié à :
info:eu-repo/semantics/altIdentifier/doi/10.1145/3382734.3404505
info:eu-repo/semantics/OpenAccess
Sujets proches
ProofCiter ce document
Laurent Feuilloley et al., « Compact Distributed Certification of Planar Graphs », HAL-SHS : économie et finance, ID : 10.1145/3382734.3404505
Métriques
Partage / Export
Résumé
Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the existence of a distributed interactive proof for planarity (i.e., for certifying that a network is planar), using a sophisticated generic technique for constructing distributed IP protocols based on sequential IP protocols. The interactive proof for planarity is based on a distributed certification of the correct execution of any given sequential linear-time algorithm for planarity testing. It involves three interactions between the prover and the randomized distributed verifier (i.e., it is a dMAM protocol), and uses small certificates, on O(log n) bits in n-node networks. We show that a single interaction from the prover suffices, and randomization is unecessary, by providing an explicit description of a proof-labeling scheme for planarity, still using certificates on just O(log n) bits. We also show that there are no proof-labeling schemes-in fact, even no locally checkable proofs-for planarity using certificates on o(log n) bits.