Seminar Upcoming

The notion of a distributed interactive proof (DIP) was introduced by Kol, Oshman, and Saxena (PODC 2018). In a DIP, the verifier seeks to verify a certain claim regarding a given input graph $G$ in a distributed fashion, i.e., operating concurrently on all $n$ nodes of $G$. The verification is done by interacting with a centralized prover that has access to the entire input graph. A DIP is measured by the amount of communication it requires. Namely, the objective is to design DIPs with a small number of interaction rounds and a small proof size, i.e., a small message size per interaction round.

We focus on the planarity task, i.e., deciding if the input graph is planar. Naor, Parter, and Yogev (SODA 2020) present a DIP for planarity with $3$ interaction rounds and a proof size of $O(\log n)$. Shortly after, Feuilloley et al. (PODC 2020) showed that the same proof size can be accomplished by a non-interactive protocol and gave a matching lower bound for the non-interactive case. In this talk, I will discuss two recent papers (DISC 2025, SODA 2026) that provide new DIP protocols with significantly improved communication bounds culminating in a protocol with only $O(\log ^{*} n)$ communication. The talk will be self-contained — no prior knowledge on planarity/distributed interactive proofs is necessary.

Based on joint work with Merav Parter.