Distributed Interactive Proofs for Planarity with Log-Star Communication

Yuval Gil, Merav Parter

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 S…