Derandomizing the Lovasz Local Lemma more effectively
| dc.creator | Moser, Robin A. | |
| dc.date | 2008-07-14 | |
| dc.date | 2008-09-15 | |
| dc.date.accessioned | 2026-07-07T10:02:27Z | |
| dc.date.available | 2026-07-07T10:02:27Z | |
| dc.description | The famous Lovasz Local Lemma [EL75] is a powerful tool to non-constructively prove the existence of combinatorial objects meeting a prescribed collection of criteria. Kratochvil et al. applied this technique to prove that a k-CNF in which each variable appears at most 2^k/(ek) times is always satisfiable [KST93]. In a breakthrough paper, Beck found that if we lower the occurrences to O(2^(k/48)/k), then a deterministic polynomial-time algorithm can find a satisfying assignment to such an instance [Bec91]. Alon randomized the algorithm and required O(2^(k/8)/k) occurrences [Alo91]. In [Mos06], we exhibited a refinement of his method which copes with O(2^(k/6)/k) of them. The hitherto best known randomized algorithm is due to Srinivasan and is capable of solving O(2^(k/4)/k) occurrence instances [Sri08]. Answering two questions asked by Srinivasan, we shall now present an approach that tolerates O(2^(k/2)/k) occurrences per variable and which can most easily be derandomized. The new algorithm bases on an alternative type of witness tree structure and drops a number of limiting aspects common to all previous methods. | |
| dc.description | 8 pages; added acknowledgement | |
| dc.identifier | https://arxiv.org/abs/0807.2120 | |
| dc.identifier | http://arxiv.org/abs/0807.2120 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/168981 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Computational Complexity | |
| dc.subject | F.2; G.2 | |
| dc.title | Derandomizing the Lovasz Local Lemma more effectively | |
| dc.type | text |