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