Computing Non-Repetitive Sequences Using the Lovász Local Lemma

Abstract: We discuss effective versions of classical results on the existence of non-repetitive sequences first proven using the Lovász Local Lemma, a non-constructive existence result from the probabilistic method. We outline the path to these constructions. First, a probabilistic resample algorithm converges to a witness to the Local Lemma in polynomial expected time. Then, the bound on the expectation is used to build a deterministic algorithm with computable convergence time. However, the resulting effective computation has constraints that make it unsuitable for constructing non-repetitive sequences. We modify the resample algorithm and show that these modifications allow us to relax these constraints

discrete mathematicslogicprobability

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic