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

Comments

Post a Comment

Popular posts from this blog

The Combinatorics 2018 conference June 3 to 9, 2018 in Arco, Province of Trento, Italy

Image
Skip to content. | Skip to navigation Search Site Advanced Search… Site Map   Accessibility   Contact   Personal tools Log in This is SunRain Plone Theme Navigation Home About us Research Groups Conferences Area privata Combinatorics 2018       You are here:   Home   /  Combinatorics 2018 Combinatorics 2018 The Combinatorics 2018 conference will be organised by the research groups of the Universities of Brescia (Catholic and State Universities), Padova, and Verona. It will take place from June 3 to 9, 2018 in Arco, Province of Trento, Italy. It will be the 20th edition of this conference held in Italy--the first one in 1981, the second in 1982, and every two years ever since--with the participation of many experts in finite geometries and their applications from all over the world. The main themes of the conference will be Finite Geometries, Incidence Structures, Combinatorial Designs and Graph Theory. Arc
Read more

Conference announcement: FQ15 13-17 June 2022, Aubervilliers, France

 https://fq15.telecom-paris.fr/ International Conference on Finite Fields and Their Applications 2022 (Fq15) The conference  Fq15  will take place at Campus Condorcet, Aubervilliers, France (on line 12 of the Paris metro, at one station from the limit of Paris) during the week of June 13-17, 2022. Fq15  will continue the 30-year-old tradition of a forum for researchers on the mathematical aspects of finite fields and their applications.  Scientific Scope Topics of interest include, but are not limited to: Theory: structure of finite fields, primitive elements, normal bases, polynomials, number-theoretic aspects of finite fields, character sums, function fields, planar functions and almost perfect nonlinear functions, equations over finite fields. Computation: algorithms and complexity, polynomial factorization, decomposition, and irreducibility testing, sequences and functions. Applications: algebraic coding theory, cryptography, algebraic geometry over finite fields, finite incidence
Read more

Conference Announcement: International Conference on Finite Fields and Their Applications 2022 (Fq15)

 https://fq15.telecom-paris.fr/ The conference  Fq15  will take place at Campus Condorcet, Aubervilliers, France (on line 12 of the Paris metro, at one station from the limit of Paris) during the week of June 13-17, 2022. Fq15  will continue the 30-year-old tradition of a forum for researchers on the mathematical aspects of finite fields and their applications. Previous editions of the  Fq  conference could be found  here . Scientific Scope Topics of interest include, but are not limited to: Theory: structure of finite fields, primitive elements, normal bases, polynomials, number-theoretic aspects of finite fields, character sums, function fields, planar functions and almost perfect nonlinear functions, equations over finite fields. Computation: algorithms and complexity, polynomial factorization, decomposition, and irreducibility testing, sequences and functions. Applications: algebraic coding theory, cryptography, algebraic geometry over finite fields, finite incidence geometry, desi
Read more