We give an algorithmic local lemma by establishing a sufficient condition for the uniform
random walk on a directed graph to reach a sink quickly. Our work is inspired by Moser's …

Ramsey theory is a fascinating topic. The author shares his view of the topic in this
contemporary overview of Ramsey theory. He presents from several points of view, adding …

The Lovasz Local Lemma is a seminal result in probabilistic combinatorics. It gives a
sufficient condition on a probability space and a collection of events for the existence of an …

While there has been significant progress on algorithmic aspects of the Lovász Local
Lemma (LLL) in recent years, a noteworthy exception is when the LLL is used in the context …

We consider the recent formulation of the algorithmic Lovász Local Lemma [N. Harvey and J.
Vondrák, in Proceedings of FOCS, 2015, pp. 1327--1345; D. Achlioptas and F. Iliopoulos, in …

Let G be an n-vertex graph that contains linearly many cherries (ie, paths on 3 vertices), and
let c be a coloring of the edges of the complete graph K n such that at each vertex every …

The Lovász local lemma is a seminal result in probabilistic combinatorics. It gives a sufficient
condition on a probability space and a collection of events for the existence of an outcome …

For any probability space and a collection of events we give an algorithmic proof of the
Lovász Local Lemma if there is a resampling oracle for each event. The resampling oracles …

Abstract The Lovasz Local Lemma (LLL) is a cornerstone principle of the probabilistic
method for combinatorics. This shows that one can avoid a large of set of “bad …

While there has been significant progress on algorithmic aspects of the Lov\'{a} sz Local
Lemma (LLL) in recent years, a noteworthy exception is when the LLL is used in the context …