BEGIN:VCALENDAR
VERSION:2.0
PRODID:researchseminars.org
CALSCALE:GREGORIAN
X-WR-CALNAME:researchseminars.org
BEGIN:VEVENT
SUMMARY:Daniel Mourad (University of Connecticut)
DTSTART:20230504T180000Z
DTEND:20230504T190000Z
DTSTAMP:20260423T035743Z
UID:OLS/116
DESCRIPTION:Title: <a href="https://researchseminars.org/talk/OLS/116/">Co
 mputing Non-Repetitive Sequences Using the  Lovász Local Lemma</a>\nby Da
 niel Mourad (University of Connecticut) as part of Online logic seminar\n\
 n\nAbstract\nWe discuss effective versions of classical results on the exi
 stence of non-repetitive sequences first proven using the Lovász Local Le
 mma\, a non-constructive existence result from the probabilistic method. W
 e outline the path to these constructions. First\, a probabilistic resampl
 e algorithm converges to a witness to the Local Lemma in polynomial expect
 ed time. Then\, the bound on the expectation is used to build a determinis
 tic algorithm with computable convergence time. However\, the resulting ef
 fective computation has constraints that make it unsuitable for constructi
 ng non-repetitive sequences. We modify the resample algorithm and show tha
 t these modifications allow us to relax these constraints\n
LOCATION:https://researchseminars.org/talk/OLS/116/
END:VEVENT
END:VCALENDAR