Renaming in distributed certification

DOI10.1016/J.TCS.2025.115643MaRDI QIDQ6884856zbMATH OpenFDO

Authors Nicolas Bousquet, L. Esperet, Laurent Feuilloley, Sébastien Zeitoun

Publication date 12 December 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115643

zbMATH Keywords

global certificateidentifierslocal certificationrenaming

Mathematics Subject Classification ID

Distributed systems (68M14) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Cites work

• Approximate proof-labeling schemes
• Brief announcement: Global certification via perfect hashing
• Communication Complexity
• Graphs which contain all small graphs
• scientific article; zbMATH DE number 3887059 (Why is no real title available?)
• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• Introduction to local certification
• Local verification of global proofs
• On the power of the congested clique model
• Optimal adjacency labels for subgraphs of Cartesian products
• Proof labeling schemes
• Simplified lower bounds on the multiparty communication complexity of disjointness
• Sparse universal graphs for planarity
• Testing Equality in Communication Graphs
• The approximate degree of DNF and CNF formulas
• The power of distributed verifiers in interactive proofs
• The renaming problem: recent developments and open questions
• Trade-offs in distributed interactive proofs

This page was built for publication: Renaming in distributed certification

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