Computing Non-Repetitive Sequences Using the Lovász Local Lemma
Daniel Mourad (University of Connecticut)
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
Series comments: Description: Seminar on all areas of logic
Organizer: | Wesley Calvert* |
*contact for this listing |