toggle visibility Search & Display Options

Select All    Deselect All
 |   | 
  Record Links
Author (up) Feuilloley, L.; Fraigniaud, P.; Montealegre, P.; Rapaport, I.; Remila, E.; Todinca, I. doi  openurl
  Title Compact Distributed Certification of Planar Graphs Type
  Year 2021 Publication Algorithmica Abbreviated Journal Algorithmica  
  Volume Early Access Issue Pages  
  Keywords Distributed algorithms; Network algorithms; Graph property certification; Labeling schemes; Planarity  
  Abstract Naor M., Parter M., Yogev E.: (The power of distributed verifiers in interactive proofs. In: 31st ACM-SIAM symposium on discrete algorithms (SODA), pp 1096-115, 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 with 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.  
  Corporate Author Thesis  
  Publisher Place of Publication Editor  
  Language Summary Language Original Title  
  Series Editor Series Title Abbreviated Series Title  
  Series Volume Series Issue Edition  
  ISSN ISBN Medium  
  Area Expedition Conference  
  Notes WOS:000648028200001 Approved  
  Call Number UAI @ alexi.delcanto @ Serial 1376  
Permanent link to this record
Select All    Deselect All
 |   | 

Save Citations:
Export Records: