A parallel algorithmic version of the local lemma

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 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 has recently found a method for converting some of these existence proofs into efficient algorithmic procedures, at the cost of loosing a little in the estimates, but his method does not seem to be parallelizable. His technique is modified to achieve an algorithmic version that can be parallelized, thus providing deterministic NC1 algorithms for various interesting algorithmic search problems.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
PublisherPubl by IEEE
Pages586-593
Number of pages8
ISBN (Print)0818624450
StatePublished - Dec 1 1991
Externally publishedYes
EventProceedings of the 32nd Annual Symposium on Foundations of Computer Science - San Juan, PR, USA
Duration: Oct 1 1991Oct 4 1991

Publication series

NameAnnual Symposium on Foundations of Computer Science (Proceedings)
ISSN (Print)0272-5428

Other

OtherProceedings of the 32nd Annual Symposium on Foundations of Computer Science
CitySan Juan, PR, USA
Period10/1/9110/4/91

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Cite this

Alon, N. (1991). A parallel algorithmic version of the local lemma. In Annual Symposium on Foundations of Computer Science (Proceedings) (pp. 586-593). (Annual Symposium on Foundations of Computer Science (Proceedings)). Publ by IEEE.