{"ID":2852249,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.18592","arxiv_id":"2510.18592","title":"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 ^{*}n)$-round DIP protocol for embedded planarity and planarity with a proof size of $O(1)$ and $O(\\lceil\\log Δ/\\log ^{*}n\\rceil)$, respectively. In fact, this result can be generalized as follows. For any $1\\leq r\\leq \\log^{*}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 Δ/r)$, respectively.","short_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 grap...","url_abs":"https://arxiv.org/abs/2510.18592","url_pdf":"https://arxiv.org/pdf/2510.18592v1","authors":"[\"Yuval Gil\",\"Merav Parter\"]","published":"2025-10-21T12:50:19Z","proceeding":"cs.DC","tasks":"[\"cs.DC\",\"cs.DS\"]","methods":"[]","has_code":false}