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 Lovász Local Lemma (LLL) shows that, for a collection of “bad” events B in a probability space that are not too likely and not too interdependent, there is a positive probability that no events in B occur. Moser and Tardos (2010) gave sequential and parallel algorithms that transformed most applications of the variable-assignment LLL into efficient algorithms. A framework of Harvey and Vondrák (2015) based on “resampling oracles” extended this to sequential algorithms for other probability spaces satisfying a generalization of the LLL known as the Lopsided Lovász Local Lemma (LLLL). We describe a new structural property that holds for most known resampling oracles, which we call “obliviousness.” Essentially, it means that the interaction between two bad-events B, B′ depends only on the randomness used to resample B and not the precise state within B itself. This property has two major consequences. First, combined with a framework of Kolmogorov (2016), it leads to a unified parallel LLLL algorithm, which is faster than previous, problem-specific algorithms of Harris (2016) for the variable-assignment LLLL and of Harris and Srinivasan (2014) for permutations. This gives the first RNC algorithms for rainbow perfect matchings and rainbow Hamiltonian cycles of Kn. Second, this property allows us to build LLLL probability spaces from simpler “atomic” events. This gives the first resampling oracle for rainbow perfect matchings on the complete s-uniform hypergraph Kn(s) and the first commutative resampling oracle for Hamiltonian cycles of Kn.

Oblivious Resampling Oracles and Parallel Algorithms for the Lopsided Lovász Local Lemma