Presburger Award 2025 – Laudatio

The 2025 Presburger Award Committee has chosen Tomasz Kociumaka and Sepehr Assadi as joint recipients of the 2025 EATCS Presburger Award for Young Scientists.

Tomasz Kociumaka has made breakthrough contributions to the field of string algorithms and data structures, solving long-standing open problems and developing near-linear time algorithms for a wide range of fundamental string problems, including pattern matching, repetitions, and compressed indexing. His work often unifies and generalizes earlier techniques, offering clean and powerful algorithmic solutions that have reshaped the understanding of core computational tasks on strings. Tomasz has advanced both the design of efficient algorithms and the underlying combinatorial insights needed to analyze them, producing results that have become central references in the area. His research has not only advanced the state of the art in text algorithms but also inspired new lines of inquiry, establishing him as a leader in the field.

Sepehr Assadi has made foundational contributions to the theory of sublinear and streaming algorithms, particularly for graph problems, where he introduced novel techniques for proving strong lower bounds and developed optimal or near-optimal algorithms for central tasks such as matching, vertex cover, and coloring. His work answered long-standing open questions about the complexity of multi-pass streaming algorithms and established deep connections between streaming and communication complexity. Sepehr’s results are not only technically innovative but have also helped shape the research agenda in graph streaming, demonstrating how to navigate the inherent trade-offs between memory, passes, and approximation. His research has significantly influenced our understanding of what can be computed under severe resource constraints and has opened new avenues for lower bound techniques in theoretical computer science.

Presburger Award Committee 2025

Tal Malkin (chair)

Joël Ouaknine

Shiri Chechik

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.