Distributed Interactive Proofs for Planarity with Log-Star Communication

Abstract

We provide new communication-efficient distributed interactive proofs for planarity. The notion of a \emph{distributed interactive proof (DIP)} was introduced by Kol, Oshman, and Saxena (PODC 2018). In a DIP, the \emph{prover} is a single centralized entity whose goal is to prove a certain claim regarding an input graph $G$. To do so, the prover communicates with a distributed \emph{verifier} that operates concurrently on all $n$ nodes of $G$. A DIP is measured by the amount of prover-verifier communication it requires. Namely, the goal is to design a DIP with a small number of interaction rounds and a small \emph{proof size}, i.e., a small amount of communication per round. Our main result is an $O({\log }^{\ast }n)$-round DIP protocol for embedded planarity and planarity with a proof size of $O(1)$ and $O(\lceil \log \hat{I}”/{\log }^{\ast }n\rceil )$, respectively. In fact, this result can be generalized as follows. For any $1\le r\le {\log }^{\ast }n$, there exists an $O(r)$-round protocol for embedded planarity and planarity with a proof size of $O({\log }^{(r)}n)$ and $O({\log }^{(r)}n+\log \hat{I}”/r)$, respectively.

To appear in SODA 26