Trade-offs in distributed interactive proofs

DOI10.4230/LIPICS.DISC.2019.13MaRDI QIDQ6487530zbMATH OpenFDO

Authors Pilu Crescenzi, Pierre Fraigniaud, Ami Paz

Publication date 3 February 2023

Full work available at URL https://doi.org/10.4230/LIPICS.DISC.2019.13

zbMATH Keywords

distributed verificationdistributed interactive proofs

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Specification and verification (program logics, model checking, etc.) (68Q60) Communication complexity, information complexity (68Q11)

Recommendations

• Interactive distributed proofs
• The power of distributed verifiers in interactive proofs
• scientific article; zbMATH DE number 4106274
• Redundancy in distributed proofs
• Redundancy in distributed proofs

Cited in

(19)

• Interactive distributed proofs
• Introduction to local certification
• Local certification of graphs with bounded genus
• A hierarchy of local decision
• Distributed Provers with Applications to Undeniable Signatures
• Local certification of geometric graph classes
• The power of distributed verifiers in interactive proofs
• Redundancy in distributed proofs
• Shared versus private randomness in distributed interactive proofs
• scientific article; zbMATH DE number 7765409 (Why is no real title available?)
• Compact distributed certification of planar graphs
• Distributed quantum proofs for replicated data
• Proof-labeling schemes: broadcast, unicast and in between
• Distributed model checking on graphs of bounded treedepth
• Renaming in distributed certification
• Twenty-two new approximate proof labeling schemes
• Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
• Distributed interactive proofs for the recognition of some geometric intersection graph classes
• The hardness of local certification of finite-state dynamics

This page was built for publication: Trade-offs in distributed interactive proofs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6487530)