Twenty-two new approximate proof labeling schemes
From MaRDI portal
Publication:6535018
DOI10.4230/lipics.disc.2020.20zbMath1540.68305MaRDI QIDQ6535018
Publication date: 2 November 2023
Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Distributed algorithms (68W15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- New inapproximability bounds for TSP
- On the hardness of approximating minimum vertex cover
- The Steiner tree problem on graphs: inapproximability results
- What can be verified locally?
- Space-time tradeoffs for distributed verification
- Distributed verification of minimum spanning trees
- Randomized proof-labeling schemes
- On distributed Merlin-Arthur decision protocols
- Proof labeling schemes
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- On the power of unique 2-prover 1-round games
- Proof-Labeling Schemes: Broadcast, Unicast and in Between
- Hardness of Distributed Optimization
- The Power of Distributed Verifiers in Interactive Proofs
- Interactive Distributed Proofs
- Analytical approach to parallel repetition
- Some optimal inapproximability results
- Optimal Inapproximability Results for MAX‐CUT and Other 2‐Variable CSPs?
- Local Distributed Decision
- Approximate proof-labeling schemes
- Error-sensitive proof-labeling schemes
- Trade-offs in distributed interactive proofs
This page was built for publication: Twenty-two new approximate proof labeling schemes
