scientific article; zbMATH DE number 7561277

DOI10.4230/LIPIcs.DISC.2018.25zbMath1497.68298arXiv1803.09553MaRDI QIDQ5090917

Laurent Feuilloley, Juho Hirvonen

Publication date: 21 July 2022

Full work available at URL: https://arxiv.org/abs/1803.09553

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

non-determinismdistributed verificationlocal proofsproof-labeling schemes

Mathematics Subject Classification ID

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

Related Items

A hierarchy of local decision ⋮ Compact distributed certification of planar graphs ⋮ Introduction to local certification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Worst-case equilibria
• Space-time tradeoffs for distributed verification
• Distributed verification of minimum spanning trees
• Proof labeling schemes
• Non-Interactive Proofs of Proximity
• The Landscape of Communication Complexity Classes.
• Communication Complexity
• Proof-Labeling Schemes: Broadcast, Unicast and in Between
• Algorithms, games, and the internet
• Proof labeling schemes
• Towards a complexity theory for local distributed computing
• Non-Deterministic Graph Property Testing
• Local Distributed Decision
• Approximate proof-labeling schemes