What can be verified locally?

DOI10.1016/j.jcss.2018.05.004zbMath1398.68167OpenAlexW2885668823WikidataQ129395629 ScholiaQ129395629MaRDI QIDQ1672006

Gianlorenzo D'Angelo, Dennis Olivetti, Alkida Balliu, Pierre Fraigniaud

Publication date: 7 September 2018

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://aaltodoc.aalto.fi/handle/123456789/35266

zbMATH Keywords

decision problemsdistributed computinglocal model

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Related Items (6)

A hierarchy of local decision ⋮ Deciding and verifying network properties locally with few output bits ⋮ A meta-theorem for distributed certification ⋮ A meta-theorem for distributed certification ⋮ Local certification of graphs with bounded genus ⋮ Introduction to local certification

Cites Work

• Unnamed Item
• Unnamed Item
• Proof labeling schemes
• Survey of local algorithms
• Locally checkable proofs
• Leveraging Linial’s Locality Limit
• Locality in Distributed Graph Algorithms
• Distributed Computing: A Locality-Sensitive Approach
• Distributed Graph Automata
• What Can be Computed Locally?
• What can be decided locally without identifiers?
• Towards a complexity theory for local distributed computing
• On the Impact of Identifiers on Local Decision
• What cannot be computed locally!

This page was built for publication: What can be verified locally?