The Gödel Prize 2020 - Laudation

The 2020 Gödel Prize is awarded to Robin A. Moser and Gábor Tardos for their algorithmic version of the Lovász Local Lemma in the paper:

“A constructive proof of the general Lovász Local Lemma," Journal of the ACM 57(2): 11:1-11:15 (2010).

The Lovász Local Lemma (LLL) is a fundamental tool of the probabilistic method. It 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 randomized algorithms matching the bounds of the existence proof. The paper further gives a derandomized 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.

Robin Moser obtained his PhD in 2012 from the Swiss Federal Institute of Technology in Zurich where he was a member of the research group of Emo Welzl. His dissertation was on Exact Algorithms for Constraint Satisfaction Problesm. His career included internships with the European Organization for Nuclear Research (CERN) in Geneva as well as with Microsoft Research in Redmond, WA. Since 2013, he has worked developing trading software and as a quantitative analyst for Circular Capital in the Basel area in Switzerland.

Gábor Tardos received a PhD in Mathematics at Eötvös University, Budapest in 1988. His advisors were László Babai and Péter Pál Pálfy. He held postdoctoral positions at the University of Chicago, Rutgers University, University of Toronto and the Institute for Advanced Study in Princeton. He was a Canada Research Chair of discrete and computational geometry at the Simon Fraser University from 2005 to 2013. After that he returned to the Alfréd Rényi Institute of Mathematics in Budapest where he has been a research fellow since 1991.

e-max.it: your social media marketing partner
 
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.