NDLI: Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model

Please wait, while we are loading the content...

New Opportunities for PODC?: Massive, Volatile, but Highly Predictable Resources

A Distributed (2+ε)-Approximation for Vertex Cover in O(logδ/ε log log δ) Rounds

Analysing Snapshot Isolation

Deterministic Objects: Life Beyond Consensus

Concurrent Data Structures

Contention Resolution on a Fading Channel

Distributed Strong Diameter Network Decomposition: Extended Abstract

Space Bounds for Reliable Storage: Fundamental Limits of Coding

How Emerging Memory Technologies Will Have You Rethinking Algorithm Design

Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation

A Faster Distributed Radio Broadcast Primitive: Extended Abstract

Search on a Line with Faulty Robots

Low-Congestion Shortcuts without Embedding

The Greedy Spanner is Existentially Optimal

Recoverable Mutual Exclusion: [Extended Abstract]

Unbeatable Set Consensus via Topological and Combinatorial Reasoning

Reliable Communication over Highly Connected Noisy Networks

Optimal Dynamic Distributed MIS

Specification and Complexity of Collaborative Text Editing

On the Complexity of Reader-Writer Locks: Extended Abstract

Broadcast Extensions with Optimal Communication and Round Complexity

Uniform Deployment of Mobile Agents in Asynchronous Rings

The Coalescing-Branching Random Walk on Expanders and the Dual Epidemic Process

MST in Log-Star Rounds of Congested Clique

A Randomized Concurrent Algorithm for Disjoint Set Union

A Polylogarithmic Gossip Algorithm for Plurality Consensus

Contention Resolution on Multiple Channels with Collision Detection

A Local Constant Factor MDS Approximation for Bounded Genus Graphs

Optimal Mobile Byzantine Fault Tolerant Distributed Storage: Extended Abstract

An Algorithm for Replicated Objects with Efficient Reads

Two-Bit Messages are Sufficient to Implement Atomic Read/Write Registers in Crash-prone Systems

Fault-Tolerant Multi-Agent Optimization: Optimal Iterative Distributed Algorithms

Ant-Inspired Density Estimation via Random Walks: Extended Abstract

Distributed Algorithms for Planar Networks I: Planar Embedding

Self-stabilizing Balls & Bins in Batches: The Power of Leaky Bins [Extended Abstract]

Noisy Rumor Spreading and Plurality Consensus

How Asynchrony Affects Rumor Spreading Time

On Efficient Distributed Construction of Near Optimal Routing Schemes: Extended Abstract

A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems

Are Shared Objects Composable under an Oblivious Adversary?

How Proofs are Prepared at Camelot: Extended Abstract

Brief Announcement: Active Information Spread in Networks

Brief Announcement: Multi-Broadcasting under the SINR Model

Brief Announcement: Labeling Schemes for Power-Law Graphs

Brief Announcement: Local Independent Set Approximation

Rational Consensus: Extended Abstract

Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model

Brief Announcement: Deterministic Graph Connectivity in the Broadcast Congested Clique

A Complexity-Based Hierarchy for Multiprocessor Synchronization: [Extended Abstract]

Brief Announcement: A Family of Leaderless Generalized-Consensus Algorithms

Brief Announcement: Proactive Secret Sharing with a Dishonest Majority

Brief Announcement: Certified Universal Gathering in $R^{2}$ for Oblivious Mobile Robots

Brief Announcement: Using Read-k Inequalities to Analyze a Distributed MIS Algorithm

Brief Announcement: Sublinear-Space Distance Labeling Using Hubs

Brief Announcement: A Tight Space Bound for Consensus

Brief Announcement: Data Dissemination in Unified Dynamic Wireless Networks

Brief Announcement: Asynchronous Coordination with Constraints and Preferences

Brief Announcement: Computing in the Presence of Weak Crash Failures

Brief Announcement: Probabilistic Asynchronous Arbitrary Pattern Formation

Brief Announcement: A Key-Value Map for Massive Real-Time Analytics

Brief Announcement: Optimal Leader Election in Multi-Hop Radio Networks

Brief Announcement: Reliable Message Transmission under Partial Knowledge and General Adversaries

Brief Announcement: Oh-RAM! One and a Half Round Read/Write Atomic Memory

Brief Announcement: Pattern Formation Problem for Synchronous Mobile Robots in the Three Dimensional Euclidean Space

Brief Announcement: The Small World of Curious Beings

Brief Announcement: Self-stabilizing Clock Synchronization with 3-bit Messages

Brief Announcement: Space-Time Tradeoffs for Distributed Verification

Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model

Content Provider	ACM Digital Library
Author	Chang, Yi-Jun Pettie, Seth Kopelowitz, Tsvi
Abstract	Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring. For most problems the best randomized algorithm is at least exponentially faster than the best deterministic algorithm. In this paper we prove that these exponential gaps are necessary and establish numerous connections between the deterministic and randomized complexities in the LOCAL model. Each of our results has a very compelling take-away message: Fast Δ-coloring of trees requires random bits. Building on the recent randomized lower bounds of Brandt et al. [6], we prove that the randomized complexity of Δ-coloring a tree with maximum degree Δ is $θ(log_{Δ}$ log n), for any Δ ≥ 55, whereas its deterministic complexity is $θ(log_{Δ}$ n) for any Δ ≥ 3. This also establishes a large separation between the deterministic complexity of Δ-coloring and (Δ+1)-coloring trees. Randomized lower bounds imply deterministic lower bounds. We prove that any deterministic algorithm for a natural class of problems that runs in O(1) + $o(log_{Δ}$ n) rounds can be transformed to run in O(log* n -- log*Δ + 1) rounds. If the transformed algorithm violates a lower bound (even allowing randomization), then one can conclude that the problem requires $Ω(log_{Δ}$ n) time deterministically. (This gives an alternate proof that deterministically Δ-coloring a tree with small Δ takes $Ω(log_{Δ}$ n) rounds.) Deterministic lower bounds imply randomized lower bounds. We prove that the randomized complexity of any natural problem on instances of size n is at least its deterministic complexity on instances of size √log n}. This shows that a deterministic $Ω(log_{Δ}$ n) lower bound for any problem (Δ-coloring a tree, for example) implies a randomized $Ω(log_{Δ}$ log n) lower bound. It also illustrates that the graph shattering technique employed in recent randomized symmetry breaking algorithms is absolutely essential to the LOCAL model. For example, it is provably impossible to improve the $2^{O}(√log$ log n) terms in the complexities of the best MIS and (Δ+1)-coloring algorithms without also improving the $2^{O}(√log$ n})-round Panconesi-Srinivasan algorithms.
Starting Page	195
Ending Page	197
Page Count	3
File Format	PDF
ISBN	9781450339643
DOI	10.1145/2933057.2933079
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2016-07-25
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Coloring Distributed algorithm Symmetry breaking
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Brief Announcement: Average Complexity for the LOCAL Model

Brief Announcement: Symmetry Breaking in the CONGEST Model: Time- and Message-Efficient Algorithms for Ruling Sets

An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model

Brief announcement: Linial's lower bound made easy

Brief announcement: Super-fast t-ruling sets

Weak graph colorings: distributed algorithms and applications

On the complexity of distributed graph coloring

A new technique for distributed symmetry breaking

Average and randomized complexity of distributed problems (1996).

Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model

Similar Documents

Brief Announcement: Average Complexity for the LOCAL Model

Brief Announcement: Symmetry Breaking in the CONGEST Model: Time- and Message-Efficient Algorithms for Ruling Sets

An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model

Brief announcement: Linial's lower bound made easy

Brief announcement: Super-fast t-ruling sets

Weak graph colorings: distributed algorithms and applications

On the complexity of distributed graph coloring

A new technique for distributed symmetry breaking

Average and randomized complexity of distributed problems (1996).

Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model