BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//University of Liverpool Computer Science Seminar System//v2//EN
BEGIN:VEVENT
DTSTAMP:20260601T200109Z
UID:Seminar-dept-1490@lxserverM.csc.liv.ac.uk
ORGANIZER:CN=Lutz Oettershagen:MAILTO:Lutz.Oettershagen@liverpool.ac.uk
DTSTART:20260616T130000
DTEND:20260616T140000
SUMMARY:School Seminar Series
DESCRIPTION:Subhajit Pramanick: Distributed Local Verification using Proofs with(out) Errors\n\nIn 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}. \n\nThe 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. \n\n\n\nOne 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$). \n\n\n\nWe 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.\n\nhttps://www.csc.liv.ac.uk/research/seminars/abstract.php?id=1490
LOCATION:Brodi tower R106
END:VEVENT
END:VCALENDAR