Compact Distributed Certification of Planar Graphs

Laurent Feuilloley (), Pierre Fraigniaud (), Pedro Montealegre (), Ivan Rapaport, Éric Rémila () and Ioan Todinca
Additional contact information
Laurent Feuilloley: UCHILE - Universidad de Chile = University of Chile [Santiago]
Pierre Fraigniaud: IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale - CNRS - Centre National de la Recherche Scientifique - UPCité - Université Paris Cité
Pedro Montealegre: Universidad Adolfo Ibáñez [Santiago]
Ivan Rapaport: CMM - Centre de modélisation mathématique / Centro de Modelamiento Matemático [Santiago] - UCHILE - Universidad de Chile = University of Chile [Santiago] - CNRS - Centre National de la Recherche Scientifique
Éric Rémila: GATE Lyon Saint-Étienne - Groupe d'Analyse et de Théorie Economique Lyon - Saint-Etienne - ENS de Lyon - École normale supérieure de Lyon - Université de Lyon - UL2 - Université Lumière - Lyon 2 - UCBL - Université Claude Bernard Lyon 1 - Université de Lyon - UJM - Université Jean Monnet - Saint-Étienne - CNRS - Centre National de la Recherche Scientifique
Ioan Todinca: LIFO - Laboratoire d'Informatique Fondamentale d'Orléans - UO - Université d'Orléans - INSA CVL - Institut National des Sciences Appliquées - Centre Val de Loire - INSA - Institut National des Sciences Appliquées

Post-Print from HAL

Abstract: 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.

Date: 2020-08-03
New Economics Papers: this item is included in nep-net
Note: View the original document on HAL open archive server: https://shs.hal.science/halshs-02991868v1
References: View complete reference list from CitEc
Citations:

Published in 39th ACM Symposium on Principles of Distributed Computing, Aug 2020, Virtual Event Italy, Italy. pp.319-328, ⟨10.1145/3382734.3404505⟩

Downloads: (external link)
https://shs.hal.science/halshs-02991868v1/document (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hal:journl:halshs-02991868

DOI: 10.1145/3382734.3404505

Access Statistics for this paper

More papers in Post-Print from HAL
Bibliographic data for series maintained by CCSD ().