Locally checkable proofs in distributed computing
From MaRDI portal
Complexity of proofs (03F20) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)
Recommendations
Cites work
Cited in
(48)- Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs
- On mobile agent verifiable problems
- Almost global problems in the LOCAL model
- Deciding and verifying network properties locally with few output bits
- Randomized proof-labeling schemes
- Redundancy in distributed proofs
- Compact distributed certification of planar graphs
- Local certification of graphs on surfaces
- Proof labeling schemes for reachability-related problems in directed graphs
- A meta-theorem for distributed certification
- Distributed interactive proofs for the recognition of some geometric intersection graph classes
- Local certification of graphs with bounded genus
- A new approach on locally checkable problems
- Planarity can be verified by an approximate proof labeling scheme in constant-time
- Emptiness problems for distributed automata
- A hierarchy of local decision
- On distributed Merlin-Arthur decision protocols
- Locally checkable proofs
- A time hierarchy theorem for the LOCAL model
- Introduction to local certification
- Redundancy in distributed proofs
- Local verification of global proofs
- Distributed Testing of Distance-k Colorings
- How proofs are prepared at Camelot (extended abstract)
- Approximate proof-labeling schemes
- scientific article; zbMATH DE number 7765409 (Why is no real title available?)
- Automated testing and interactive construction of unavoidable sets for graph classes of small path‐width
- A meta-theorem for distributed certification
- Compact Distributed Interactive Proofs for the Recognition of Cographs and Distance-Hereditary Graphs
- The complexity landscape of distributed locally checkable problems on trees
- Twenty-two new approximate proof labeling schemes
- Brief announcement: Distributed quantum proofs for replicated data
- The hardness of local certification of finite-state dynamics
- Locally verifiable distributed SNARGs
- Distributed model checking on graphs of bounded treedepth
- Local certification of local properties: tight bounds, trade-offs and new parameters
- Decreasing verification radius in local certification
- Local certification of local properties: tight bounds, trade-offs, and new parameters
- Compact distributed certification of geometric graph classes
- A LOCAL view of the polynomial hierarchy
- On the power of quantum distributed proofs
- Brief announcement: Distributed model checking on graphs of bounded treedepth
- Brief announcement: Local advice and local decompression
- A subquadratic certification scheme for P₅-free graphs
- Shared versus private randomness in distributed interactive proofs
- Distributed quantum proofs for replicated data
- Local certification of geometric graph classes
- Reductions in local certification
This page was built for publication: Locally checkable proofs in distributed computing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3179347)
