Distributed verification and hardness of distributed approximation
From MaRDI portal
Recommendations
Cited in
(65)- The lower bounds on distributed shortest paths
- Local checkability, no strings attached: (a)cyclicity, reachability, loop free updates in SDNs
- On efficient distributed construction of near optimal routing schemes
- On mobile agent verifiable problems
- Distributed verification of minimum spanning trees
- Broadcast and minimum spanning tree with \(o(m)\) messages in the asynchronous CONGEST model
- Fast distributed approximation for TAP and 2-edge-connectivity
- Randomized proof-labeling schemes
- Redundancy in distributed proofs
- Compact distributed certification of planar graphs
- Local certification of graphs with bounded genus
- Approximate minimum directed spanning trees under congestion
- Latency, capacity, and distributed minimum spanning trees
- Sublinear-time distributed algorithms for detecting small cliques and even cycles
- What can be sampled locally?
- The sparsest additive spanner via multiple weighted BFS trees
- A hierarchy of local decision
- Detecting cliques in CONGEST networks
- Fooling views: a new lower bound technique for distributed computations under congestion
- Message lower bounds via efficient network synchronization
- Locality and checkability in wait-free computing
- A distributed enumeration algorithm and applications to all pairs shortest paths, diameter\dots
- Proof-labeling schemes: broadcast, unicast and in between
- A distributed algorithm for directed minimum-weight spanning tree
- Message Lower Bounds via Efficient Network Synchronization
- Fast distributed approximation for TAP and 2-edge-connectivity
- An Unconditional Lower Bound on the Time-Approximation Trade-off for the Distributed Minimum Spanning Tree Problem
- Hardness of discrepancy computation and \(\varepsilon\)-net verification in high dimension
- Near-Optimal Approximate Shortest Paths and Transshipment in Distributed and Streaming Models
- Computing exact minimum cuts without knowing the graph
- A deterministic almost-tight distributed algorithm for approximating single-source shortest paths
- Distributed spanner approximation
- Lower bounds for approximating graph parameters via communication complexity
- Distributed Exact Weighted All-Pairs Shortest Paths in Randomized Near-Linear Time
- Distributed approximate maximum matching in the CONGEST model
- Redundancy in distributed proofs
- Time-message trade-offs in distributed algorithms
- Faster distributed shortest path approximations via shortcuts
- Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model
- The Sparsest Additive Spanner via Multiple Weighted BFS Trees
- Distributed Testing of Distance-k Colorings
- Distributed graph algorithms and their complexity: an introduction
- Veracity radius, capturing the locality of distributed computations
- Distributed computation of large-scale graph problems
- Distributed verification and hardness of distributed approximation
- Approximate proof-labeling schemes
- Communication costs in a geometric communication network
- Minimum cost flow in the CONGEST model
- Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions
- (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings
- Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model
- Asynchronous Wait-Free Runtime Verification and Enforcement of Linearizability
- Maximum length-constrained flows and disjoint paths: distributed, deterministic, and fast
- Finding a small vertex cut on distributed networks
- Distributed planar reachability in nearly optimal time
- On packing low-diameter spanning trees
- Distributed model checking on graphs of bounded treedepth
- Tight bounds on the message complexity of distributed tree verification
- Deterministic expander routing: faster and more versatile
- Computing minimum weight cycle in the CONGEST model
- Polylogarithmic time algorithms for shortest path forests in programmable matter
- Asynchronous wait-free runtime verification and enforcement of linearizability
- Distance computations in the hybrid network model via oracle simulations
- Polylogarithmic time algorithms for shortest path forests in programmable matter
- hop-constrained oblivious routing
This page was built for publication: Distributed verification and hardness of distributed approximation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4907581)
