Name
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.
|
Year | DOI | Venue |
|---|---|---|
2020 | 10.1145/3382734.3404505 | PODC '20: ACM Symposium on Principles of Distributed Computing
Virtual Event
Italy
August, 2020 |
DocType | ISBN | Citations |
Conference | 978-1-4503-7582-5 | 0 |
PageRank | References | Authors |
0.34 | 0 | 6 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Laurent Feuilloley | 1 | 19 | 6.49 |
| Pierre Fraigniaud | 2 | 2849 | 220.78 |
| Pedro Montealegre | 3 | 28 | 11.47 |
| Ivan Rapaport | 4 | 2 | 1.72 |
| Eric Rémila | 5 | 329 | 45.22 |
| Ioan Todinca | 6 | 328 | 27.33 |