Twenty-two new approximate proof labeling schemes

DOI10.4230/LIPICS.DISC.2020.20MaRDI QIDQ6535018zbMATH OpenFDO

Authors Yuval Emek, Yuval Gil

Publication date 2 November 2023

Full work available at URL https://doi.org/10.4230/LIPICS.DISC.2020.20

zbMATH Keywords

approximation algorithmsdistributed graph problemsproof-labeling schemes

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Approximation algorithms (68W25)

Recommendations

• Approximate proof-labeling schemes
• Approximate proof-labeling schemes
• Proof labeling schemes
• Planarity can be verified by an approximate proof labeling scheme in constant-time
• Randomized proof-labeling schemes

Cites work

• Analytical approach to parallel repetition
• Approximate proof-labeling schemes
• Distributed verification of minimum spanning trees
• Error-sensitive proof-labeling schemes
• Hardness of Distributed Optimization
• Interactive distributed proofs
• Local Distributed Decision
• Locally checkable proofs in distributed computing
• New inapproximability bounds for TSP
• On distributed Merlin-Arthur decision protocols
• On the hardness of approximating minimum vertex cover
• On the power of unique 2-prover 1-round games
• Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
• Proof labeling schemes
• Proof-labeling schemes: broadcast, unicast and in between
• Randomized proof-labeling schemes
• Redundancy in distributed proofs
• Some optimal inapproximability results
• Survey of distributed decision
• The power of distributed verifiers in interactive proofs
• The Steiner tree problem on graphs: inapproximability results
• Trade-offs in distributed interactive proofs
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• What can be verified locally?

Cited in

(3)

• Planarity can be verified by an approximate proof labeling scheme in constant-time
• Local certification of local properties: tight bounds, trade-offs and new parameters
• Local certification of local properties: tight bounds, trade-offs, and new parameters

This page was built for publication: Twenty-two new approximate proof labeling schemes

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