Ehemaliger Doktorand Robin Moser erhält renommierten Gödel-​Preis

The paper, titled "A constructive proof of the general Lovász Local Lemma", was published in the Journal of the ACM 57(2): 11:1-11:15 in 2010 together with author Prof. Gábor Tardos. It discusses the Lovász Local Lemma (LLL), a fundamental tool of the probabilistic method which enables one to show the existence of certain objects even though they occur with exponentially small probability.

The original proof was not algorithmic, and subsequent algorithmic versions had significant losses in parameters. This paper provides a simple, powerful algorithmic paradigm that converts almost all known applications of the LLL into randomised algorithms matching the bounds of the existence proof. The paper further gives a derandomised algorithm, a parallel algorithm, and an extension to the "lopsided" LLL.

The new algorithmic paradigm involves resampling variables that cause bad events. Such resampling was subsequently used in numerous other papers, including ones that don't directly relate to the LLL. Moreover, the paper provides an elegant proof of correctness involving witness trees. Witness trees have been influential well beyond the LLL, inspiring the "entropy compression" method in combinatorics. Overall, the paper's power and simplicity make it a far-reaching achievement.

About Robin Moser

Robin Moser obtained his doctoral degree in 2012 from the Department of Computer Science, ETH Zurich, where he was a member of Prof. Emo Welzl’s research group. His dissertation was on “Exact Algorithms for Constraint Satisfaction Problems”. His career included internships with the European Organization for Nuclear Research (CERN) in Geneva as well as with Microsoft Research in Redmond, Washington, USA.

Since 2013, he has worked developing trading software and as a quantitative analyst for Circular Capital in the Basel area in Switzerland.