Presburger Award 2022 – Laudatio for Dor Minzer

The 2022 Presburger Award Committee has unanimously selected

Dor Minzer

as the recipient of the 2022 EATCS Presburger Award for Young Scientists for his deep technical contributions towards resolving the 2-to-2 Games Conjecture.

The Unique Games Conjecture, formulated in 2002, is one of the central open questions in theoretical computer science, providing a plausible explanation of the hardness of approximation for a variety of natural problems, and weaving connections between computational complexity, algorithms, analysis, and geometry. While the jury is still out on this conjecture, the closely related variant of the 2-to-2 Games Conjecture was recently resolved by Minzer and his co-authors over a remarkable series of four papers between 2017 and 2018. "Lesser" variant notwithstanding, it has several important consequences, including establishing the hardness of distinguishing between almost-4-colourable graphs from almost-k-colourable graphs for constant k, and ruling out a polynomial-time-vs-truly-exponential-time dichotomy for approximating constraint satisfaction problems.

The proof of the 2-to-2 Games Conjecture involves a complex process of reformulating and reducing it to a concrete combinatorial hypothesis about the expansion properties of Grassmann graphs, and then proving this hypothesis using tools from the analysis of Boolean functions.

Minzer has also to his credit other strong and insightful results, in areas spanning property testing, information complexity, invariance and isoperimetry, noise sensitivity, and more. Minzer's work establishes him as a world leader in Boolean function analysis, an area central to obtaining and understanding many diverse and significant advances in theoretical computer science.

Presburger Award Committee 2022

Mikołaj Bojanczyk (University of Warsaw)

Uriel Feige (The Weizmann Institute, Israel)

Meena Mahajan (The Institute of Mathematical Sciences, Chennai, chair)

The Presburger Award is awarded by the European Association for Theoretical Computer Science (EATCS) to a young scientist 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.