12/12/2018, 10h30, LIP6 24-25 room 405

Title: Redundancy in Distributed Proofs
Abstract:
Distributed proofs are mechanisms enabling the nodes of a network to collectively and efficiently check the correctness of Boolean predicates on the structure of the network (e.g. having a specific diameter), or on data-structures distributed over the nodes (e.g. a spanning tree). We show that many network predicates have distributed proofs offering a high level of redundancy, explicitly or implicitly. We use this remarkable property of distributed proofs for establishing perfect tradeoffs between the size of the certificate stored at every node, and the number of rounds of the verification protocol.

Joint work with Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvone
and Mor Perry.