Former doctoral student Robin Moser receives prestigious Gödel Prize
Amanda Caracas | 06.04.2020
One of the most prestigious prizes in the area of theoretical computer science has been awarded to Robin Moser for his algorithmic version of the Lovász Local Lemma.
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.
About the Gödel Prize
The Gödel Prize for outstanding papers in the area of theoretical computer science is sponsored jointly by the European Association for Theoretical Computer Science (EATCS) and the Special Interest Group on Algorithms and Computation Theory of the Association for Computing Machinery (ACM SIGACT). This award is presented annually.
The 28th Gödel Prize will be awarded at the 47th International Colloquium on Automata, Languages, and Programming to be held during 8-11 July 2020 in Saarbrücken, Germany. The prize is named in honour of Kurt Gödel in recognition of his major contributions to mathematical logic.