Distributed Interactive Proofs for Planarity with Log-Star Communication
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866912663004512256 |
|---|---|
| author | Gil, Yuval Parter, Merav |
| author_facet | Gil, Yuval Parter, Merav |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_18592 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Distributed Interactive Proofs for Planarity with Log-Star Communication Gil, Yuval Parter, Merav Distributed, Parallel, and Cluster Computing Data Structures and Algorithms 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. |
| title | Distributed Interactive Proofs for Planarity with Log-Star Communication |
| topic | Distributed, Parallel, and Cluster Computing Data Structures and Algorithms |
| url | https://arxiv.org/abs/2510.18592 |