A parallel algorithmic version of the local lemma

Research output: Contribution to journalArticle

109 Scopus citations

Abstract

The Lovasz Local Lemma is a tool that enables one to show that certain events hold with positive, though very small probability. It often yields existence proofs of results without supplying any efficient way of solving the corresponding algorithmic problems. J. Beck recently has found a method for converting some of these existence proofs into efficient algorithmic procedures, at the cost of losing a little in the estimates. His method does not seem to be parallelizable. Here we modify his technique and achieve an algorithmic version that can be parallelized, thus obtaining deterministic NCl algorithms for several interesting algorithmic problems.

Original languageEnglish (US)
Pages (from-to)367-378
Number of pages12
JournalRandom Structures & Algorithms
Volume2
Issue number4
DOIs
StatePublished - 1991
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'A parallel algorithmic version of the local lemma'. Together they form a unique fingerprint.

  • Cite this