Uma versão algorítmica do Lema Local de Lovász - Cavalar, Bruno Pasqualotto (Anais do Encontro de Teoria da Computação (ETC), 2017)
O Lema Local de Lovász (LLL) é uma ferramenta poderosa para provar a existência de objetos combinatórios que satisfazem um dado conjunto de restrições. Mais precisamente, dado uma coleção finita A de eventos “ruins”, o LLL dá condições suficientes para que a probabilidade P [∩ A∈A Ā] seja positiva. Em um celebrado artigo [Moser and Tardos 2010], Moser e Tardos desenvolveram um algoritmo para encontrar eficientemente tais objetos cuja existência é garantida pelo LLL. Esse trabalho discute aplicações do LLL em problemas de combinatória e aplica o algoritmo de Moser e Tardos nesses problemas.