Opening book details…
Can I read A Breezing Proof of the KMW Bound on EtoBox?
A Breezing Proof of the KMW Bound by Corinna Coupette; Christoph Lenzen is a book available to read on EtoBox.
What is A Breezing Proof of the KMW Bound about?
In their seminal paper from 2004, Kuhn, Moscibroda, and Wattenhofer (KMW) proved a hardness result for several fundamental graph problems in the LO-CAL model: For any (randomized) algorithm, there are graphs with n nodes and maximum degree ∆ on which Ω(min{ log n/ log log n, log ∆/ log log ∆}) (expected) communication rounds are required to obtain polylogarithmic approximations to a minimum vertex cover, minimum dominating set, or maximum matching. Via reduction, this hardness extends to symmetry breaking tasks like finding maximal independent sets or maximal matchings. Today, more than 15 years later, there is still no proof of this result that is easy on the reader. Setting out to change this, in this work, we provide a simplified proof of the main step in showing the KMW lower bound. Our key argument is algorithmic, and it relies on an invariant that can be readily verified from the generation rules of the lower bound graphs.
- Author
- Corinna Coupette; Christoph Lenzen
- Publisher
- Society for Industrial and Applied Mathematics
- Published
- 2021
- Language
- EN
More by Corinna Coupette; Christoph Lenzen
Browse all works by Corinna Coupette; Christoph Lenzen
Similar books
- A Fast Minimum Degree Algorithm and Matching Lower Bound — Robert Cummings; Matthew Fahrbach; Animesh Fatehpuria (2021)
- A Nearly-Linear Bound for Chasing Nested Convex Bodies — C.J. Argue; Sébastien Bubeck; Michael B. Cohen; Anupam Gupta; Yin Tat Lee (2019)
- On Computing the Hyperbolicity of Real-World Graphs — Michele Borassi; David Coudert; Pierluigi Crescenzi; Andrea Marino (2015)
- How to Morph Graphs on the Torus — Erin Wolf Chambers; Jeff Erickson; Patrick Lin; Salman Parsa (2021)
- Parallel Batch-Dynamic k-Clique Counting — Laxman Dhulipala; Quanquan C. Liu; Julian Shun; Shangdi Yu (2021)
- Tight Bounds for Online Graph Partitioning — Monika Henzinger; Stefan Neumann; Harald Räcke; Stefan Schmid (2021)