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

Daniel Mourad (University of Connecticut)

04-May-2023, 18:00-19:00 (19 months ago)

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

Organizer: Wesley Calvert*
*contact for this listing

Export talk to