Distributed Local Verification using Proofs with(out) Errors

16^th June 2026, 13:00 Brodi tower R106
Subhajit Pramanick
University of Wroclaw

Abstract

In distributed graph algorithms, a yes-no verification (sometimes called certification) of graph properties requires the following. (1) for a yes-instance, all nodes must output 1 (or accept), and (2) for a no-instance, at least one node must output 0 (or reject). A popular framework in this context is verification using locally checkable proofs (LCP), introduced by Goos and Suomela, which is a verification scheme involving a \emph{prover} and a \emph{verifier}.
The prover has access to the graph and assigns the \emph{proof labels} on graph nodes. The verifier is a distributed algorithm running on every node that distinguishes between yes and no instances, using the proof labels of the node and the nodes within a constant $k$ radius neighborhood. The parameter $k$ is called the view distance of a node. Under this framework, if a graph $G$ satisfies a given property $\mathcal{P}$, then there exists a proof under which the verifier makes all nodes accept, whereas if the property is not satisfied, then for every proof on the graph, the verifier makes at least one node reject.

One important metric in this context is the proof size, i.e., the maximum number of bits used in any proof label for a node. We are going to discuss about two verticals: \emph{oracular proofs}, where the prover assigns correct proof labels on the nodes, and \emph{erroneous proofs}, where an adversary can corrupt parts of the oracular proof with a goal of misleading the verifier. In the context of oracular proofs, one verification problem of our interest is to verify whether the graph contains a cycle or not. We call it cycle existence. This can be verified using a constant-sized proof. We can construct a proof with 3 distinct proof labels when nodes have a view distance of 1, but it is impossible to construct a proof with 2 proof labels for cycle existence. What is more interesting in cycle existence is that, with a cost of $3$-hop view distance for every node, we can construct a proof to encode a sense of direction (a popular technique to design proofs for different verification problems) on each edge using only $2$ labels (using a repeated use of a special string $001101$).

We have another vertical of results, which concerns erroneous proofs, as mentioned earlier. We consider a setting in which the adversary is allowed to modify proof labels of at most $i$ nodes within the $2i+1$-hop neighborhood of each node. To tackle this, we introduce an algorithmic framework \textbf{\texttt{refix}} that requires every node to have a view distance of $2i+1$. Although we could not prove that \framework{} works for any verification problem or provide a formal classification of verification problems that can be verified using \framework{}, we illustrate its applicability to three verification problems: cycle existence, cycle-freeness, and bipartiteness. We establish a lower bound to demonstrate a correlation between $i$ and the view distance required for every node.

Biography

I am currently a postdoctoral researcher at the University of Wroclaw, Poland, under the supervision of Prof. Tomasz Jurdzinski. Prior to that, I completed my PhD from the Indian Institute of Technology Guwahati under the supervision of Prof. Partha Sarathi Mandal. My current research interests primarily focus on distributed graph algorithms.