The TAU Programming Languages and Systems Seminar - Distributed Proof Labeling Schemes

Abstract:

Proof labeling schemes are "the distributed version" of NP: in order to verify that our network satisfies some desired property, each network node receives an advice string, and the nodes exchange their advice with their neighbors and decide whether the property holds or not. Poof labeling schemes were originally conceived as a mechanism by which a distributed decision algorithm can store a short "certificate of correctness" at every network node; however, in light of the rise of cloud computing, there is now also interest in thinking of an actual powerful prover that interacts with the distributed system and tries to help its computation.

In this talk I will survey a few classical ideas in the area of proof labeling schemes, including both upper and lower bounds. Then I will present recent work on adding interaction with the prover (from a PODC paper last year, which is the precursor to the work Eylon Yogev presented in the seminar a few weeks ago).