Distributed Interactive Proofs for Planarity with Log-Star Communication
Yuval Gil, Merav Parter · 2025
Read Distributed Interactive Proofs for Planarity with Log-Star Communication by Yuval Gil, Merav Parter (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-18592.txt.
Introduction
Yuval Gil and Merav Parter design a way for a network of computers to prove together that a graph is planar, meaning it can be drawn without crossing edges. One central prover makes the claim, while a verifier runs at every node of the graph at once. The challenge is keeping the conversation between prover and nodes tiny, both in rounds and in message size.
Their protocol needs only a very slowly growing number of rounds, a quantity so slow it barely rises with graph size, and constant-size proofs for the embedded version of the problem. A flexible trade-off lets designers choose fewer rounds at the cost of slightly larger proofs. The result shows that a global geometric fact about a huge network can be certified with remarkably little communication, useful where bandwidth at each node is scarce.
Catalog record
| CREATOR | Yuval Gil, Merav Parter |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 114 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2510-18592
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Distributed Interactive Proofs for Planarity with Log-Star Communication Thanks: This project is partially funded by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme, grant agreement No. 949083 Yuval Gil, Merav Parter Abstract 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 G . To do so, the prover communicates with a distributed verifier that operates concurrently on all n n nodes of G 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 proof size , i.e., a small amount of communication per round. In prior work, Naor, Parter, and Yogev (SODA 2020) presented a 3 3 -round DIP protocol for planarity with a proof size of O ( log n ) 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 5 -round protocol with a proof size of O ( log log n ) 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 Δ ) O(\log\log n+\log\Delta) for (non-embedded) planarity, where Δ \Delta 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 ) O(\log^{*}n) -round DIP protocol for embedded planarity and planarity with a proof size of O ( 1 ) O(1) and O ( ⌈ log Δ / log ∗ n ⌉ ) O(\lceil\log\Delta/\log^{*}n\rceil) , respectively. In fact, this result can be generalized as follows. For any 1 ≤ r ≤ log ∗ n 1\leq r\leq\log^{*}n , there exists an O ( r ) O(r) -round protocol for embedded planarity and planarity with a proof size of O ( log ( r ) n ) O(\log^{(r)}n) and O ( log ( r ) n + log Δ / r ) O(\log^{(r)}n+\log\Delta/r) , respectively. 1 1 1 The function log ( r ) n \log^{(r)}n is defined recursively such that log ( 1 ) n = log n \log^{(1)}n=\log n and log ( r ) n = log ( log ( r − 1 ) n ) \log^{(r)}n=\log(\log^{(r-1)}n) . As an important step towards our main result, we also provide a 3 3 -round DIP protocol for embedded planarity and planarity with a proof size of O ( log log n ) O(\log\log n) and O ( log log n + log Δ ) O(\log\log n+\log\Delta) , respectively. This improves the round complexity of the protocol of Gil and Parter from 5 5 to 3 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. 1 Introduction The concept of interactive proofs, introduced by Goldwasser, Micali, and Rackoff [ GMR89 ] and Babai [ Bab85 ] , generalizes nondeterminism by allowing a computationally weak verifier to interact with a powerful (yet unreliable) prover. This paradigm has since become fundamental in various domains such as cryptography and complexity theory. In recent years, the increasing prevalence of distributed systems naturally leads to the question of how such proof systems can be adapted to scenarios where the computation is spread across a large-scale communication network. This motivated the introduction of distributed interactive proofs (DIPs) by Kol, Oshman, and Saxena [ KOS18 ] . In the DIP setting, the verifier consists of n nodes connected by a communication graph G . The prover is a single centralized entity that can see the entire graph and generates its proof by means of a back-and-forth interaction with all nodes. The main complexity measures of a DIP protocol are the number of interaction rounds and the proof size, i.e., the size of the largest message sent during the protocol. This paper focuses on the task of planarity , i.e., deciding if a given graph is planar. Due to the inherent global nature of planarity testing [ GH16 ] , it is only natural to explore the power that can be gained from interacting with a global prover in the DIP setting. The distributed verification of planarity has recently garnered significant attention. The first non-trivial DIP result for planarity was given by Naor, Parter, and Yogev [ NPY20 ] in the form of a 3 -round protocol with O(\log n) proof size. 2 2 2 The protocol of [ NPY20 ] is part of a more general compiler that transforms an O(n) -time computation in the RAM model into a 3 -round DIP with a proof size of O(\log n) . The protocol for planarity then follows from plugging in a linear-time planarity testing algorithm (e.g., [ HT74 ] ). Soon after, Feuilloley et al. [ FFM+21 , FFM+23 ] showed that the same proof size can be achieved for the planarity task without interaction or randomization, i.e., they provided a proof labeling scheme for planarity with a proof size of O(\log n) . This result is complemented by a matching \Omega(\log n) lower bound for planarity even in graphs of maximum degree 3 . The same lower bound was later shown to apply also when the verifier is randomized [ GP25 ] . Following the work of Feuilloley et al., the primary remaining question was whether a sub-logarithmic proof size is possible if interaction is allowed. In a very recent work [ GP25 ] , Gil and Parter provided a positive answer to this question. In particular, it is shown that there is a 5 -round DIP for planarity with a proof size of O(\log\log n+\log\Delta) in graphs of maximum degree \Delta . In addition, a 5 -round DIP with a proof size of O(\log\log n) is provided for embedded planarity, outerplanarity, series-parallel graphs, and graphs of treewidth 2 , where the embedded planarity task is defined such that a graph drawing is given in