NDLI: Distributed algorithms for the Lovász local lemma and graph coloring

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

Rational and resilient protocols

Signature-free asynchronous byzantine consensus with t < n/3 and $o(n^{2})$ messages

The future(s) of shared data structures

Multi-message broadcast with abstract MAC layers and unreliable links

Anonymous networks: randomization = 2-hop coloring

Estimation for monotone sampling: competitiveness and customization

Coding theory for scalable media delivery

Distributed connectivity decomposition

Complexity tradeoffs for read and update operations

Software-improved hardware lock elision

Trade-offs between selection complexity and performance when searching the plane without communication

An incomplete history of concurrency chapter 1. 1965--1977

Rigorous system design

How to withstand mobile virus attacks, revisited

Efficient lock-free binary search trees

Beyond geometry: towards fully realistic wireless models

Making objects writable

Asynchronous MPC with a strict honest majority using non-equivocation

A paradox of eventual linearizability in shared memory

Consensus with an abstract MAC layer

Beyond set disjointness: the communication complexity of finding the intersection

Distributed algorithms for the Lovász local lemma and graph coloring

Can quantum communication speed up distributed computation?

Concurrent updates with RCU: search tree as an example

A generalized asynchronous computability theorem

Improved distributed steiner forest construction

Born and raised distributively: fully distributed non-interactive adaptively-secure threshold signatures with short shares

The amortized complexity of non-blocking binary search trees

On the impact of geometry on ad hoc communication in wireless networks

Asynchronous convex hull consensus in the presence of crash faults

Distributing the setup in universally composable multi-party computation

Brief announcement: are lock-free concurrent algorithms practically wait-free?

Simple and efficient local codes for distributed stable network construction

Breathe before speaking: efficient information dissemination despite noisy, limited and anonymous communication

Brief announcement: towards security and privacy for outsourced data in the multi-party setting

Optimal gossip with direct addressing

Brief announcement: distributed universality: contention-awareness; wait-freedom; object progress, and other properties

Balls-into-leaves: sub-logarithmic renaming in synchronous message-passing systems

Spanners and sparsifiers in dynamic streams

Fast and unconditionally secure anonymous channel

Brief announcement: gracefully degrading consensus and k-set agreement under dynamic link failures

On the power of the congested clique model

Distributed computing building blocks for rational agents

Brief announcement: a generic construction for nonblocking dual containers

Linear-in-delta lower bounds in the LOCAL model

Brief announcement: game theoretical approach for energy-delay balancing in distributed duty-cycled MAC protocols of wireless networks

Brief announcement: concurrency-aware linearizability

Dynamic-sized nonblocking hash tables

Time versus cost tradeoffs for deterministic rendezvous in networks

Brief announcement: local approximability of minimum dominating set on planar graphs

Brief announcement: Linial's lower bound made easy

Near-optimal communication-time tradeoff in fault-tolerant computation of aggregate functions

Brief announcement: Super-fast t-ruling sets

Brief announcement: almost-tight approximation distributed algorithm for minimum cut

Distributed algorithms for the Lovász local lemma and graph coloring

Content Provider	ACM Digital Library
Author	Chung, Kai-Min Pettie, Seth Su, Hsin-Hao
Abstract	The Lovasz Local Lemma (LLL), introduced by Erdos and Lovasz in 1975, is a powerful tool of the probabilistic method that allows one to prove that a set of n "bad" events do not happen with non-zero probability, provided that the events have limited dependence. However, the LLL itself does not suggest how to find a point avoiding all bad events. Since the work of Beck (1991) there has been a sustained effort to find a constructive proof (i.e. an algorithm) for the LLL or weaker versions of it. In a major breakthrough Moser and Tardos (2010) showed that a point avoiding all bad events can be found efficiently. They also proposed a distributed/parallel version of their algorithm that requires $O(log^{2}$ n) rounds of communication in a distributed network. In this paper we provide two new distributed algorithms for the LLL that improve on both the efficiency and simplicity of the Moser-Tardos algorithm. For clarity we express our results in terms of the symmetric LLL though both algorithms deal with the asymmetric version as well. Let p bound the probability of any bad event and d be the maximum degree in the dependency graph of the bad events. When $epd^{2}$ < 1 we give a truly simple LLL algorithm running in $O(log_{1/epd^{2}}$ n) rounds. Under the tighter condition ep(d+1) < 1, we give a slightly slower algorithm running in $O(log^{2}$ d⋅ $log_{1/ep(d+1)}$ n) rounds. Furthermore, we give an algorithm that runs in sublogarithmic rounds under the condition p⋅ f(d) < 1, where f(d) is an exponential function of d. Although the conditions of the LLL are locally verifiable, we prove that any distributed LLL algorithm requires Ω(log* n) rounds. In many graph coloring problems the existence of a valid coloring is established by one or more applications of the LLL. Using our LLL algorithms, we give logarithmic-time distributed algorithms for frugal coloring, defective coloring, coloring girth-4 (triangle-free) and girth-5 graphs, edge coloring, and list coloring.
Starting Page	134
Ending Page	143
Page Count	10
File Format	PDF
ISBN	9781450329446
DOI	10.1145/2611462.2611465
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2014-07-15
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Constructive algorithm Locality Probabilistic method Distributed graph coloring
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

Distributed algorithms for the lovász local lemma and graph coloring.

A lower bound for the distributed Lovász local lemma

A Meeting Point of Probability, Graphs, and Algorithms: The Lovász Local Lemma and Related Results—A Survey

Sublogarithmic Distributed Algorithms for Lov\'asz Local Lemma, and the Complexity Hierarchy

Stochastic Local Search and the Lovasz Local Lemma

A quantum lovász local lemma

Deterministic algorithms for the lovász local lemma (2009).

Deterministic algorithms for the Lovász Local Lemma

On the complexity of distributed graph coloring

Distributed algorithms for the Lovász local lemma and graph coloring

Similar Documents

Distributed algorithms for the lovász local lemma and graph coloring.

A lower bound for the distributed Lovász local lemma

A Meeting Point of Probability, Graphs, and Algorithms: The Lovász Local Lemma and Related Results—A Survey

Sublogarithmic Distributed Algorithms for Lov\'asz Local Lemma, and the Complexity Hierarchy

Stochastic Local Search and the Lovasz Local Lemma

A quantum lovász local lemma

Deterministic algorithms for the lovász local lemma (2009).

Deterministic algorithms for the Lovász Local Lemma

On the complexity of distributed graph coloring

Distributed algorithms for the Lovász local lemma and graph coloring