Distributed Interactive Proofs for Planarity with Log-Star Communication

We provide new communication-efficient distributed interactive proofs for planarity. The notion of a distributed interactive proof (DIP) was introduced by Kol, Oshman, and Saxena (PODC 2018). In a DIP, the 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 verifier that operates concurrently on all n nodes of G. A DIP is measured by the amount of proververifier communication it requires. Namely, the goal is to design a DIP with a small number of interaction rounds and a small proof size, i.e., a small amount of communication per round.

In prior work, Naor, Parter, and Yogev (SODA 2020) presented a 3-round DIP protocol for planarity with a proof size of O(log n). Later on, Feuilloley et al. (PODC 2020) showed that the same proof size can be accomplished with a non-interactive protocol. In a very recent work by Gil and Parter (DISC 2025), a 5-round protocol with a proof size of O(log log n) is presented for embedded planarity, which is defined such that an embedding of the graph is given (e.g., each node holds a clockwise ordering of its incident edges) and the goal is to decide if it is a valid planar embedding. In addition, Gil and Parter presented a protocol with a proof size of O(log log n+log ∆) for (non-embedded) planarity, where ∆ is the maximum degree of the graph.

In this work, we design DIP protocols that significantly improve the communication bounds of Gil and Parter. 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(⌈log ∆/ log * n⌉), respectively. In fact, this result can be generalized as follows. For any 1 ≤ r ≤ 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. 1 As an important step towards our main result, we also provide a 3-round DIP protocol for embedded planarity and planarity with a proof size of O(log log n) and O(log log n+ log ∆), respectively. This improves the round complexity of the protocol of Gil and Parter from 5 to 3 while maintaining the same proof size.

One of the tools that we develop in order to obtain the main result is a novel self-reduction for a task in which two bitstrings are encoded in a distributed manner and we wish to test whether they are equal. Specifically, we show that solving this equality task can be reduced to solving a constant number of equality tasks on exponentially smaller instances. This self-reduction only requires a constant number of interaction rounds. We believe that this self-reduction could be of independent interest.