Presburger Award 2020 - Laudatio for Dmitriy Zhuk

The 2020 Presburger Award Committee has unanimously selected

Dmitriy Zhuk

as the recipient of the 2020 EATCS Presburger Award for Young Scientists, for solving one of the most important and difficult problems in the theory of computation, the CSP dichotomy conjecture of Feder and Vardi.

Constraint satisfaction is a subject of central significance in computer science, since a very large number of combinatorial problems, starting from Boolean Satisfiability and Graph Coloring, can be phrased as constraint satisfaction problems. In the nineties, Feder and Vardi conjectured that the CSP class exhibits a dichotomy, so all CSP instances are either tractable or NP-complete. This conjecture has a remarkably wide scope and inspired an extensive research programme, bringing together techniques from combinatorics and graph theory, logic and database theory, algebra and group theory.

Dmitriy Zhuk presented in 2017 a positive solution to the CSP dichotomy conjecture. A different proof of the conjecture was simultaneously and independently published by Andrei Bulatov. Zhuk’s (and Bulatov’s) proof is heavily based on the algebraic approach and the connection between universal algebra and CSP, that was established in the late nineties. The algebraic approach was gradually developed over the last 20 years, through sustained efforts of many researchers, who provided steady progress on a conjectured algebraic boundary for tractable CSPs. Zhuk’s algorithm for resolving the algebraic conjecture is an ingenious combination of consistency checking, recursion, and learning procedures for affine spaces, and brings novel techniques that already have and will have further applications in the area of CSP and beyond.

Presburger Award Committee 2020

Thore Husfeldt

Meena Mahajan

Anca Muscholl (chair)

The Presburger Award is given to a young scientist (in exceptional cases to several young scientists) for outstanding contributions in theoretical computer science, documented by a published paper or a series of published papers. The award is named after Mojżesz Presburger who accomplished his path-breaking work on decidability of the theory of addition (which today is called Presburger arithmetic) as a student in 1929. The list of the previous recipients of the Presburger Award is available at http://eatcs.org/index.php/presburger