Compact Distributed Certification of Planar Graphs
Laurent Feuilloley
(1)
,
Pierre Fraigniaud
(2)
,
Pedro Montealegre
(3)
,
Ivan Rapaport
(4)
,
Éric Rémila
(5)
,
Ioan Todinca
(6)
1
UCHILE -
Universidad de Chile = University of Chile [Santiago]
2 IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale
3 Universidad Adolfo Ibáñez [Santiago]
4 CMM - Centre de modélisation mathématique / Centro de Modelamiento Matemático [Santiago]
5 GATE Lyon Saint-Étienne - Groupe d'Analyse et de Théorie Economique Lyon - Saint-Etienne
6 LIFO - Laboratoire d'Informatique Fondamentale d'Orléans
2 IRIF (UMR_8243) - Institut de Recherche en Informatique Fondamentale
3 Universidad Adolfo Ibáñez [Santiago]
4 CMM - Centre de modélisation mathématique / Centro de Modelamiento Matemático [Santiago]
5 GATE Lyon Saint-Étienne - Groupe d'Analyse et de Théorie Economique Lyon - Saint-Etienne
6 LIFO - Laboratoire d'Informatique Fondamentale d'Orléans
Laurent Feuilloley
- Fonction : Auteur
- PersonId : 177191
- IdHAL : laurent-feuilloley
- ORCID : 0000-0002-3994-0898
Pierre Fraigniaud
- Fonction : Auteur
- PersonId : 835294
Pedro Montealegre
- Fonction : Auteur
- PersonId : 8324
- IdHAL : pedro-montealegre
- IdRef : 204368898
Éric Rémila
- Fonction : Auteur
- PersonId : 745868
- IdHAL : eric-remila
- ORCID : 0000-0002-9265-9907
- IdRef : 104534591
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.
Format du dépôt | Fichier |
---|---|
Type de dépôt | Communication dans un congrès |
Résumé |
en
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.
|
Titre |
en
Compact Distributed Certification of Planar Graphs
|
Auteur(s) |
Laurent Feuilloley
1
, Pierre Fraigniaud
2
, Pedro Montealegre
3
, Ivan Rapaport
4
, Éric Rémila
5
, Ioan Todinca
6
1
UCHILE -
Universidad de Chile = University of Chile [Santiago]
( 142796 )
- Av. Libertador Bernardo O'Higgins 1058, Santiago de Chile
- Chili
2
IRIF (UMR_8243) -
Institut de Recherche en Informatique Fondamentale
( 1005016 )
- Université de Paris
Bâtiment Sophie Germain, Case courrier 7014
8 Place Aurélie Nemours
75205 Paris Cedex 13
- France
3
Universidad Adolfo Ibáñez [Santiago]
( 301544 )
- Diagonal Las Torres 2640, Santiago, Región Metropolitana
- Chili
4
CMM -
Centre de modélisation mathématique / Centro de Modelamiento Matemático [Santiago]
( 1812 )
- Av. Blanco Encalada 2120, Piso 7 2120 SANTIAGO DE CHILE
- Chili
5
GATE Lyon Saint-Étienne -
Groupe d'Analyse et de Théorie Economique Lyon - Saint-Etienne
( 102550 )
- 93, chemin des Mouilles 69130 Écully
6, rue Basse des Rives 42023 Saint-Étienne cedex 02
- France
6
LIFO -
Laboratoire d'Informatique Fondamentale d'Orléans
( 241078 )
- Bâtiment IIIA, Rue Léonard de Vinci, B.P. 6759, F-45067 ORLEANS Cedex 2
- France
|
Actes |
Oui
|
Date de publication |
2020
|
Titre de la collection |
PODC '20: Proceedings of the 39th Symposium on Principles of Distributed Computing
|
Page/Identifiant |
319-328
|
Titre du congrès |
39th ACM Symposium on Principles of Distributed Computing
|
Date fin congrès |
2020-08-06
|
URL du congrès ou éditeur |
https://www.podc.org/history/#history
|
Langue du document |
Anglais
|
Vulgarisation |
Non
|
Comité de lecture |
Oui
|
Invité |
Non
|
Audience |
Internationale
|
Date début congrès |
2020-08-03
|
Ville |
Virtual Event Italy
|
Pays |
Italie
|
Domaine(s) |
|
Éditeur commercial |
|
Projet(s) ANR |
|
DOI | 10.1145/3382734.3404505 |
Origine :
Fichiers produits par l'(les) auteur(s)
Loading...