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/

Zendy Plus

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

Zendy Tools

Zendy Open

The Lopsided Lov\'{a}sz Local Lemma (LLLL) is a powerful probabilisticprinciple which has been used in a variety of combinatorial constructions.While originally a general statement about probability spaces, it has recentlybeen transformed into a variety of polynomial-time algorithms. The resamplingalgorithm of Moser & Tardos (2010) is the most well-known example of this. Avariety of criteria have been shown for the LLLL; the strongest possiblecriterion was shown by Shearer, and other criteria which are easier to usecomputationally have been shown by Bissacot et al (2011), Pegden (2014),Kolipaka & Szegedy (2011), and Kolipaka, Szegedy, Xu (2012).  We show a new criterion for the Moser-Tardos algorithm to converge. Thiscriterion is stronger than the LLLL criterion; this is possible because it doesnot apply in the same generality as the original LLLL; yet, it is strong enoughto cover many applications of the LLLL in combinatorics. We show a variety ofnew bounds and algorithms. A noteworthy application is for $k$-SAT, withbounded occurrences of variables. As shown in Gebauer, Sz\'{a}bo, and Tardos(2011), a $k$-SAT instance in which every variable appears $L \leq\frac{2^{k+1}}{e (k+1)}$ times, is satisfiable. Although this bound isasymptotically tight (in $k$), we improve it to $L \leq \frac{2^{k+1} (1 -1/k)^k}{k-1} - \frac{2}{k}$ which can be significantly stronger when $k$ issmall.  We introduce a new parallel algorithm for the LLLL. While Moser & Tardosdescribed a simple parallel algorithm for the Lov\'{a}sz Local Lemma, anddescribed a simple sequential algorithm for a form of the Lopsided Lemma, theywere not able to combine the two. Our new algorithm applies in nearly allsettings in which the sequential algorithm works --- this includes settingscovered by our new stronger LLLL criterion.

Lopsidependency in the Moser-Tardos framework: Beyond the Lopsided Lovasz Local Lemma