Presburger Award 2019 - Laudatio for Karl Bringmann and Kasper Green Larsen

The 2019 Presburger Award Committee has unanimously selected

Karl Bringmann and Kasper Green Larsen

as the recipients of the 2019 EATCS Presburger Award for Young Scientists, for their groundbreaking work on lower bounds.

Computer Science is the discipline of the information age, and often credited for what it can do. However, some of the best work in the discipline are the negative results: the theories and reductions that establish the impossibility of computational tasks, often providing exceptional insight into the nature of computation. The recipients of the 2019 Presburger Award represent outstanding examples of this scientific approach.

Karl Bringmann is recognised for his influential work on tight complexity bounds for polynomial-time problems, evidenced by his paper "Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails" (Symposium on Foundations of Computer Science, 2014). Bringmann’s tight lower bounds under the Strong Exponential Time Hypothesis (SETH) for several classical algorithmic problems explain the long-standing lack of algorithmic progress beyond the textbook technique of dynamic programming. Bringmann’s paper on Fréchet distance triggered a highly successful line of research for many other classical problems, including sequence similarity problems such as edit distance, longest common subsequence, tree edit distance, and compressed string problems.

Kasper Green Larsen has made a series of outstanding contributions to our understanding of the theoretical limits of computation for fundamental algorithmic tasks. To this end, Larsen has developed entirely new approaches and techniques for showing lower bounds, overcoming long-standing barriers. An early example is the ground-breaking information-theoretical lower bound in the cell probe model in his paper "The cell probe complexity of dynamic range counting" (Symposium on Theory of Computing, 2012). Since then, Larsen has continued to explore the limitations of computational models and algorithmic building blocks in many other areas, including celebrated hardness results in data structures, cryptography, and machine learning.

Presburger Award Committee 2019

Thore Husfeldt

Anca Muscholl

Jukka Suomela (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