A meta-theorem for distributed certification
From MaRDI portal
Publication:2097341
DOI10.1007/978-3-031-09993-9_7OpenAlexW4285284525MaRDI QIDQ2097341
Pierre Fraigniaud, Ioan Todinca, Ivan Rapaport, Pedro Montealegre
Publication date: 11 November 2022
Full work available at URL: https://arxiv.org/abs/2112.03195
Graph theory (including graph drawing) in computer science (68R10) Computer system organization (68Mxx) Communication complexity, information complexity (68Q11)
Related Items
Lower bound for constant-size local certification ⋮ Local certification of graphs with bounded genus
Cites Work
- Unnamed Item
- Unnamed Item
- Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques
- Graph minors. III. Planar tree-width
- Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
- A partial k-arboretum of graphs with bounded treewidth
- The local detection paradigm and its applications to self-stabilization
- What can be verified locally?
- Randomized proof-labeling schemes
- A hierarchy of local decision
- Proof labeling schemes
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Deciding First-Order Properties of Nowhere Dense Graphs
- Twin-width I: Tractable FO Model Checking
- The Power of Distributed Verifiers in Interactive Proofs
- Interactive Distributed Proofs
- Towards a complexity theory for local distributed computing
- Approximate proof-labeling schemes
