English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

We explore the power of interactive proofs with a distributed verifier. Inthis setting, the verifier consists of $n$ nodes and a graph $G$ that definestheir communication pattern. The prover is a single entity that communicateswith all nodes by short messages. The goal is to verify that the graph $G$belongs to some language in a small number of rounds, and with smallcommunication bound, i.e., the proof size.  This interactive model was introduced by Kol, Oshman and Saxena (PODC 2018)as a generalization of non-interactive distributed proofs. They demonstratedthe power of interaction in this setting by constructing protocols for problemsas Graph Symmetry and Graph Non-Isomorphism -- both of which require proofs of$\Omega(n^2)$-bits without interaction.  In this work, we provide a new general framework for distributed interactiveproofs that allows one to translate standard interactive protocols to oneswhere the verifier is distributed with short proof size. We show the following:* Every (centralized) computation that can be performed in time $O(n)$ can betranslated into three-round distributed interactive protocol with $O(\log n)$proof size. This implies that many graph problems for sparse graphs havesuccinct proofs.  * Every (centralized) computation implemented by either a small space or byuniform NC circuit can be translated into a distributed protocol with $O(1)$rounds and $O(\log n)$ bits proof size for the low space case and $polylog(n)$many rounds and proof size for NC.  * We show that for Graph Non-Isomorphism, there is a 4-round protocol with$O(\log n)$ proof size, improving upon the $O(n \log n)$ proof size of Kol etal.  * For many problems we show how to reduce proof size below the naturallyseeming barrier of $\log n$. We get a 5-round protocols with proof size $O(\log\log n)$ for a family of problems.

The Power of Distributed Verifiers in Interactive Proofs