论文标题
紧凑的平面图分布式认证
Compact Distributed Certification of Planar Graphs
论文作者
论文摘要
NAOR，PARTER和YOGEV（SODA 2020）最近证明了平面度的存在\ Emph {分布式交互式证明}（即，用于使用基于顺序IP协议构建分布式IP协议的复杂通用技术来证明网络是平面的）。平面性的交互式证明基于对平面测试的任何给定的顺序线性时间算法的正确执行的分布式认证。它涉及供者和随机分布式验证者之间的三个交互（即，它是\ dmam \/协议），并在$ o（\ log n）$ bits上使用$ n $ node网络的$ o（\ log n）$ bits上使用小证书。我们表明，通过提供平面性的\ emph {proof-labeling方案}的明确描述，从供奉献者中的单个交互就足够了，并且随机化是不必要的，但仍然仅在$ o（\ log n）$位上使用证书。我们还表明，使用$ o（\ log n）$ bits上的证书，没有证明标签的计划 - 实际上，即使没有\ emph {本地可检查的证明}。
Naor, Parter, and Yogev (SODA 2020) have recently demonstrated the existence of a \emph{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 \emph{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 \emph{locally checkable proofs} -- for planarity using certificates on $o(\log n)$ bits.
