An alternate proof of the algorithmic Lovász local lemma

Ioannis Giotis, Lefteris Kirousis, Kostas I. Psaromiligkos, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


The algorithm for Lovász Local Lemma by Moser and Tardos gives a constructive way to prove the existence of combinatorial objects satisfying a system of constraints. We present an alternative probabilistic analysis of the algorithm that does not involve reconstructing the history of the algorithm. We apply our technique to improve the best known upper bound to acyclic chromatic index.

Original languageEnglish (US)
Pages (from-to)61-65
Number of pages5
JournalTrends in Mathematics
StatePublished - 2017

ASJC Scopus subject areas

  • General Mathematics


Dive into the research topics of 'An alternate proof of the algorithmic Lovász local lemma'. Together they form a unique fingerprint.

Cite this