A meta-theorem for distributed certification

DOI10.1007/978-3-031-09993-9_7OpenAlexW4285284525MaRDI QIDQ2097341FDOQ2097341

Authors: Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Ioan Todinca 

Publication date: 11 November 2022

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

zbMATH Keywords

fault-tolerancedistributed decisionlocally checkable proofproof-labeling scheme

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)

Cites Work

• A partial k-arboretum of graphs with bounded treewidth
• Proof labeling schemes
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Graph structure and monadic second-order logic. A language-theoretic approach
• Graph minors. III. Planar tree-width
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• The local detection paradigm and its applications to self-stabilization
• Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques
• Towards a complexity theory for local distributed computing
• A hierarchy of local decision
• What can be verified locally?
• Locally checkable proofs in distributed computing
• Randomized proof-labeling schemes
• Interactive distributed proofs
• The power of distributed verifiers in interactive proofs
• Approximate proof-labeling schemes
• Twin-width. I: Tractable FO model checking

Cited In (4)

• Local certification of graphs with bounded genus
• Locally verifiable distributed SNARGs
• On mixed connectivity certificates
• The hardness of local certification of finite-state dynamics

This page was built for publication: A meta-theorem for distributed certification

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