### 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 NC^{1} algorithms for various interesting algorithmic search problems.

Original language | English (US) |
---|---|

Title of host publication | Annual Symposium on Foundations of Computer Science (Proceedings) |

Publisher | Publ by IEEE |

Pages | 586-593 |

Number of pages | 8 |

ISBN (Print) | 0818624450 |

State | Published - Dec 1 1991 |

Externally published | Yes |

Event | Proceedings of the 32nd Annual Symposium on Foundations of Computer Science - San Juan, PR, USA Duration: Oct 1 1991 → Oct 4 1991 |

### Publication series

Name | Annual Symposium on Foundations of Computer Science (Proceedings) |
---|---|

ISSN (Print) | 0272-5428 |

### Other

Other | Proceedings of the 32nd Annual Symposium on Foundations of Computer Science |
---|---|

City | San Juan, PR, USA |

Period | 10/1/91 → 10/4/91 |

### All Science Journal Classification (ASJC) codes

- Hardware and Architecture

## Cite this

*Annual Symposium on Foundations of Computer Science (Proceedings)*(pp. 586-593). (Annual Symposium on Foundations of Computer Science (Proceedings)). Publ by IEEE.