Presburger Award 2012
The Presburger Award Committee 2012, consisting of Monika Henzinger, Antonin Kucera, and Stefano Leonardi (chair) has unanimously decided to propose Venkatesan Guruswami (Carnegie Mellon University, Pittsburgh) and Mihai Patrascu (AT&T Labs, New York) as joint recipients of the 2012 EATCS Presburger Award for young scientists. (pdf)
Venkatesan Guruswami, born in 1976, has contributed cornerstone results to the theory of list decoding of error correcting codes. His work culminated in a publication with his former student Artri Rudra that gave constructions of error-correcting codes with a list-decoding algorithm that achieve minimum possible redundancy.
It settles one of the most salient theoretical open problem in the theory of communication since Shannon´s invention of error correcting codes in 1949.
The first major result of Venkatesan Guruswami in the field was given in his PhD dissertation where together with his advisor Madhu Sudan he showed how to list-decode Reed-Solomon codes beyond the traditional bound (1-R)/2. On the way to his more recent results, he developed, jointly with Piotr Indyk, new constructions of error correcting codes that allowed list decoding in nearly linear time. All these results were possible by establishing novel unexpected deep connections between computational complexity, coding theory, randomness and computation. Venkatesan Guruswami also contributed fundamental results to the theory of inapproximability and probabilistically checkable proofs.
Mihai Patrascu, born in 1982, has contributed fundamental results on lower bounds for data structures.
Despite his very young age, Mihai Patrascu's work has broken through many old barriers on fundamental data structure problems, not only revitalizing but also revolutionizing a field that was almost silent for over a decade.
The first cornerstone result was the logarithmic lower bound for dynamic search trees in the cell probe model published at SODA 2004 together with his advisor Erik Demaine. This result was followed at STOC 2004 with the logarithmic lower bound for dynamic trees, thus matching the upper bound of Sleator and Tarjan from 1983.
(Mihai Patrascu is the non-alphabetic first author in both papers.)
Key to these and later progresses was the deep information-theoretic understanding of computation developed in Mihai's work, which views the source of hardness in many problems as the same fundamental barrier in the representation and movement of information. In his work at FOCS 2008, Mihai Patrascu gave a simple common proof for many of his previous cell-probe lower bounds, connecting problems ranging from computational geometry
to graph algorithms, by reduction from a well-identified hard computational core.
The committee has recommended the EATCS Council to share the 2012 Presburger Award between Venkatasan Guruswami and Mihai Patrascu. These two outstanding young scientists, both working in different fields at a different stage of their career, fully deserve the award. This decision has been approved by the EATCS Council.