Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Wednesday, April 06, 2011
Kanellakis and Grace Murray Hopper Prizes
The ACM announced several award winners today. Two of particular interest to the theory community.
Craig Gentry,recipient of theGrace Murray Hopper Awardfor his breakthrough construction of a fully homomorphic encryption scheme, which enables computations to be performed on encrypted data without unscrambling it. This long-unsolved mathematical puzzle requires immense computational effort, but Gentry’s innovative approach broke the theoretical barrier to this puzzle by double encrypting the data in such a way that unavoidable errors could be removed without detection. This insight has the potential to result in adaptable cryptography methods that can prevent security breaches and protect sensitive personal data. Gentry is a researcher at IBM. In 2009, he won the ACM Doctoral Dissertation Award. The Hopper Award recognizes the outstanding young computer professional of the year.
Kurt Mehlhorn,recipient of theParis Kanellakis Theory and Practice Awardfor contributions to algorithm engineering that led to creation of the Library of Efficient Data Types and Algorithms (LEDA). This software collection of data structures and algorithms, which Mehlhorn developed with Stefan Näher, provides practical solutions for problems that had previously impeded progress in computer graphics, computer-aided geometric design, scientific computation, and computational biology. LEDA’s software has been incorporated in the applied research programs of thousands of companies worldwide in telecommunications, bioinformatics, Computer-Aided Design (CAD) and Geographic Information System (GIS), banking, optical products, and transportation. Since 2001, LEDA has been developed and distributed by Algorithmic Solutions Software GmbH, founded by Mehlhorn with Näher and Christian Uhrig, who introduced a novel distribution model that is free to researchers and licensed to companies. Mehlhorn is the founding director of the Max Planck Institute for Informatics and a professor at Saarland University in Saarbrucken, Germany. A Fellow of ACM, he received the Gottfried Wilhelm Leibniz Prize in 1986, and the European Association for Theoretical Computer Science (EATCS) Award in 2010. The Kanellakis Award honors specific theoretical accomplishments that significantly affect the practice of computing.