TY - GEN

T1 - A parallel algorithmic version of the local lemma

AU - Alon, Noga

PY - 1991/12/1

Y1 - 1991/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0026400779&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026400779&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:0026400779

SN - 0818624450

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 586

EP - 593

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

PB - Publ by IEEE

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

Y2 - 1 October 1991 through 4 October 1991

ER -