A meta-theorem for distributed certification

DOI10.1007/978-3-031-09993-9_7MaRDI QIDQ2097341zbMATH OpenOpenAlexFDO

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

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)