English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

The famous Lovasz Local Lemma [EL75] is a powerful tool to non-constructivelyprove the existence of combinatorial objects meeting a prescribed collection ofcriteria. Kratochvil et al. applied this technique to prove that a k-CNF inwhich each variable appears at most 2^k/(ek) times is always satisfiable[KST93]. In a breakthrough paper, Beck found that if we lower the occurrencesto O(2^(k/48)/k), then a deterministic polynomial-time algorithm can find asatisfying assignment to such an instance [Bec91]. Alon randomized thealgorithm and required O(2^(k/8)/k) occurrences [Alo91]. In [Mos06], weexhibited a refinement of his method which copes with O(2^(k/6)/k) of them. Thehitherto best known randomized algorithm is due to Srinivasan and is capable ofsolving O(2^(k/4)/k) occurrence instances [Sri08]. Answering two questionsasked by Srinivasan, we shall now present an approach that toleratesO(2^(k/2)/k) occurrences per variable and which can most easily bederandomized. The new algorithm bases on an alternative type of witness treestructure and drops a number of limiting aspects common to all previousmethods.

Derandomizing the Lovasz Local Lemma more effectively