Presburger Award 2024 – Laudatio

The 2024 Presburger Award Committee has chosen Justin Hsu and Pravesh Kothari as joint recipients of the 2024 EATCS Presburger Award for Young Scientists.

Justin Hsu has made deep and seminal contributions to the field of probabilistic program analysis and automated verification, and in particular has developed robust semantic and logical foundations for probabilistic and conditional independence, which are critical for analyzing randomized computations. These independence notions are essential for achieving tight accuracy bounds and formally establishing various security and privacy properties of randomized computations through, among others, concentration inequalities. Prior to Justin's groundbreaking work, the absence of logical foundations for reasoning about independence significantly limited the formal analysis of probabilistic programs. One of Justin's key insights was to introduce a novel probabilistic interpretation of bunched and separation logics, treating the separating conjunction * ("star") as conditional independence. This endeavor was especially challenging because these logics, originally developed by O'Hearn and Reynolds for spatial analysis of heap-manipulating programs, involve complex semantic domains. Justin's work was a technical tour de force; numerous previous attempts to build probabilistic semantics for these logics had failed. Justin's contributions have enabled the automated verification of many randomized algorithms previously out of the reach of formal methods, and have spurred several promising research directions in the semantics and verification of probabilistic programs.

Pravesh Kothari is a leader in the design of algorithms for handling random and semi-random input instances. In his work he developed insightful proof techniques that are of interest beyond their initial intended use. Pravesh, together with different sets of coauthors, has many outstanding contributions. He designed algorithms based on the sum-of-squares (SOS) hierarchy for handling random and semi random inputs of constraint satisfaction problems, graph problems, and problems in learning and robust statistics, solving several known open problems in these areas. This was complemented by establishing pseudo-calibration as a technique for proving nearly tight lower bounds for algorithms in the SOS hierarchy. He developed techniques for using and analysing Kikuchi matrices in the context of refutation algorithms for semi-random input instances. A surprising outcome of this work is a proof that a previously open conjecture in combinatorics is indeed true, the so called ``Moore bound'' for hypergraphs. Most recently, he used these techniques to improve the known lower bounds on the block length of locally decodable codes, and to dramatically improve the lower bounds for (linear) locally correctable codes. Overall, the work of Pravesh exemplifies how the best kind of research is done in theoretical computer science, developing new and powerful techniques that lead to breakthroughs in his main research area, and successfully applying these techniques to achieve breakthroughs in additional areas, thus forming new connections between different research areas.

Presburger Award Committee 2024

Uriel Feige (chair)

Tal Malkin

Joël Ouaknine

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.