Distributed verification and hardness of distributed approximation

DOI10.1137/11085178XMaRDI QIDQ4907581zbMATH OpenOpenAlexFDO

Authors Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, Roger Wattenhofer, David Peleg

Publication date 4 February 2013

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/11085178x

zbMATH Keywords

lower boundsdistributed algorithmscommunication complexityhardness of approximationgraph optimization problems

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15) Network design and communication in computer systems (68M10)

Recommendations

• Distributed verification and hardness of distributed approximation
• Distributed verification of minimum spanning trees
• Randomized Lower Bound for Distributed Spanning-Tree Verification

Cited in

(64)

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

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)