Presburger Award 2023 – Laudatio

The 2023 Presburger Award Committee has unanimously selected

Aaron Bernstein and Thatchaphol Saranurak

as joint recipients of the 2023 EATCS Presburger Award for Young Scientists.

The 2023 Presburger Award Committee has chosen Aaron Bernstein and Thatchaphol Saranurak as joint recipients of the 2023 EATCS Presburger Award for Young Scientists. These two remarkable individuals have emerged as leaders in the field of fast graph algorithms, focusing their research on core problems such as shortest paths, connectivity, and matching. These problems have long been central to computer science, driving advancements in education, research, and real-world applications.

Aaron Bernstein has spearheaded a new wave of major breakthroughs in fast graph algorithms, with numerous achievements authored by him or inspired by his original ideas. Several techniques that by now are part of the toolbox for the design of graph algorithms are largely due to Aaron. These include edge-degree constrained subgraphs and hopsets for undirected graphs, and low diameter decompositions for directed graphs. These techniques, as used by Aaron and others, have made a profound impact on fundamental graph problems such as shortest paths and maximum matching, in multiple settings, including sequential, dynamic, distributed, online, parallel, sublinear, and streaming. A notable recent example of his groundbreaking work is a near linear time algorithm for the single source shortest path problem in directed graphs, allowing for edges of negative weights.

Thatchaphol Saranurak has made remarkable strides in the design of efficient graph algorithms, often solving long standing open problems. In his work, Thatchaphol developed techniques that are of general interest and of high impact. A notable such technique is expander decomposition. Thatchapol introduced and applied it successfully in new settings such as dynamic graph algorithms and directed graphs. Moreover, Thatchaphol designed new efficient constructions of expander decompositions, in sequential settings as well as in distributed ones. Thatchaphol’s many results span a wide range of graph problems,  including nearly best possible algorithms for classical problems such as vertex connectivity and all pairs max flow, and groundbreaking work on dynamic algorithms for problems such as spanning forests and matching.

Presburger Award Committee 2023

Mikołaj Bojanczyk (chair)

Uriel Feige

Tal Malkin

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.