Combinatorics in the news

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, with the presentation taking place alternately at the International Colloquium on Automata, Languages, and Programming (ICALP) and the ACM Symposium on Theory of Computing (STOC). The 28th Gödel Prize will be awarded at the 47th International Colloquium on Automata, Languages, and Programming to be held during 8–12 July, 2020 in Beijing. The Prize is named in honour of Kurt Gödel in recognition of his major contributions to mathematical logic and of his interest, discovered in a letter he wrote to John von Neumann shortly before Neumann’s death, in what has become the famous “P versus NP” question. The Prize includes an award of USD 5,000.

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 Problems. 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.

http://www.sigact.org/prizes/g%C3%B6del.html