Approximate proof-labeling schemes

DOI10.1016/j.tcs.2018.08.020zbMath1437.68193OpenAlexW3022323839MaRDI QIDQ5919426

Keren Censor-Hillel, Ami Paz, Mor Perry

Publication date: 13 February 2020

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2018.08.020

zbMATH Keywords

approximation algorithmsprimal-dual algorithmsdistributed verificationdistributed graph algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (9)

Planarity can be verified by an approximate proof labeling scheme in constant-time ⋮ Lower bound for constant-size local certification ⋮ A hierarchy of local decision ⋮ A meta-theorem for distributed certification ⋮ Redundancy in distributed proofs ⋮ A meta-theorem for distributed certification ⋮ Distributed interactive proofs for the recognition of some geometric intersection graph classes ⋮ Local certification of graphs with bounded genus ⋮ Introduction to local certification

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fast and compact self-stabilizing verification, computation, and fault detection of an MST
• Node labels in local decision
• Near-linear lower bounds for distributed distance computations, even in sparse networks
• Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs
• Space-time tradeoffs for distributed verification
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Distributed verification of minimum spanning trees
• Proof labeling schemes
• Locality and checkability in wait-free computing
• Randomized Proof-Labeling Schemes
• Optimal distributed all pairs shortest paths and applications
• Distributedly Testing Cycle-Freeness
• Distributed Algorithms for Network Diameter and Girth
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication)
• Communication Complexity
• Distributed Verification and Hardness of Distributed Approximation
• What can be decided locally without identifiers?
• Better Approximation Algorithms for the Graph Diameter
• Towards a complexity theory for local distributed computing
• Fast approximation algorithms for the diameter and radius of sparse graphs
• On the Impact of Identifiers on Local Decision

This page was built for publication: Approximate proof-labeling schemes