Twenty-two new approximate proof labeling schemes
From MaRDI portal
Publication:6535018
DOI10.4230/LIPICS.DISC.2020.20zbMATH Open1540.68305MaRDI QIDQ6535018FDOQ6535018
Authors: Yuval Emek, Yuval Gil 
Publication date: 2 November 2023
Recommendations
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Distributed algorithms (68W15)
Cites Work
- Proof labeling schemes
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- On the hardness of approximating minimum vertex cover
- The Steiner tree problem on graphs: inapproximability results
- On the power of unique 2-prover 1-round games
- Analytical approach to parallel repetition
- Distributed verification of minimum spanning trees
- Local Distributed Decision
- New inapproximability bounds for TSP
- Survey of distributed decision
- What can be verified locally?
- Locally checkable proofs in distributed computing
- Randomized proof-labeling schemes
- On distributed Merlin-Arthur decision protocols
- Interactive distributed proofs
- Proof-labeling schemes: broadcast, unicast and in between
- Redundancy in distributed proofs
- The power of distributed verifiers in interactive proofs
- Approximate proof-labeling schemes
- Error-sensitive proof-labeling schemes
- Trade-offs in distributed interactive proofs
- Hardness of Distributed Optimization
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)
