More than 145 papers in computer science, electrical engineering and mathematical sciences published in refereed conference proceedings and journals in 2009 were submitted by IBM Research authors worldwide for the 2009 Pat Goldberg Memorial Best Paper Awards in CS, EE and Math.
The overall quality of the papers submitted was high. From these submissions, the Research Professional Interest Communities (PICs) nominated 35 papers based on technical significance (depth and breadth) and expected impact on computer science, electrical engineering or mathematical sciences, or their applications in the research disciplines covered by the PICs.
A committee consisting of the PIC site coordinators (see sidebar) and head of IBM Computer Science Laura Hass reviewed the nominated papers and selected the following four as winners of the 2009 Pat Goldberg Memorial Best Paper Awards. In alphabetical order:
Author and affiliation: Craig Gentry -- IBM Watson
Paper title: Fully Homomorphic Encryption Using Ideal Lattices
Name of journal or conference: STOC 2009
The subject of Gentry's paper -- and main achievement – concerns a public-key encryption scheme with the property that computation can be carried out on encrypted data without having to decrypt the data. This would allow users, for example, to store their documents and e-mails in the cloud in an encrypted state and to have the cloud provider search through that data and return the matching documents without ever having to decrypt them. Many other applications are possible. The technique represents a huge breakthrough for potential use in privacy-preserving applications, such as the management of large databases or the sharing of information with minimal privacy leakage. Not only does this have obvious technological benefits, but it comes at a time where data confidentiality and privacy are major concerns for the successful functioning of the "electronic society." The emerging "cloud computing" models, where information and computation are outsourced to not-fully-trusted computers or organizations confirms the timeliness of these results.
This paper has spawned a new research area in practical fully homomorphic encryption and enabled new applied crypto techniques that build on its results. In the year since it was published in STOC, a top conference for computer science theory, more than 55 papers have been published that cite it and build on it. And at the most recent (2010) Crypto conference (a top conference for cryptography), about 15-20% of the papers were using, citing or building on Gentry's paper. Craig Gentry has received the Privacy Innovation Award from International Association of Privacy Professionals. His work was the subject of a Forbes article.
Authors and affiliation: Yu-Ming Lin, Keith A. Jenkins, Alberto Valdes-Garcia, Joshua P. Small, Damon B. Farmer, and Phaedon Avouris -- IBM T. J. Watson Research Center
Paper title: Operation of Graphene Transistors at Gigahertz Frequencies
Name of journal or conference: Nano Letters
Despite intense activities on graphene research, the intrinsic high-frequency transport properties of graphene transistors have not been studied systematically. This paper presents the first comprehensive experimental studies on the high-frequency response of top-gated graphene transistors for different gate voltages and gate lengths. The main contribution: The paper demonstrates a peak cutoff frequency fT as high as 26 GHz measured for a 150 nm gate graphene transistor, establishing the state of the art for graphene transistors. These results also indicate that if the high mobility of graphene can be preserved during the device fabrication process, a cutoff frequency approaching terahertz may be achieved for graphene FET with a smaller gate length.
Note: As a part of the continuous effort, the authors recently published a paper in Science magazine (Feb 2010) announcing the demonstration of a radio-frequency graphene transistor with the highest cut-off frequency achieved so far by any graphene device ("100-GHz Transistors from Wafer-Scale Epitaxial Graphene").
Authors and affiliation: Amol Ghoting and Konstantin Makarychev -- IBM Research
Paper title: Serial and Parallel Methods for I/O Efficient Suffix Tree Construction (via ACM portal)
Name of journal or conference: 35th SIGMOD International conference on Management of Data
The authors revisit a fundamental data structure in string processing, namely the suffix tree. By doing a thorough review of past work, the authors highlight the main deficiencies of existing solutions and then introduce robust and scalable techniques to address these deficiencies. In greater detail, the authors identify the following limitations in past work: (a) existing suffix-tree construction approaches take a considerable amount of time to construct the data structure, when provided with large input strings; (b) existing approaches require either the input string to fit in memory, or when this restriction is not present, the approaches have poor access patterns that result in significant I/O latency. To address these limitations, the authors propose an external memory algorithm for building a suffix tree which works by (i) forming an exact frequency histogram of sub-strings, and (ii) using it to identify a set of sub-strings of the input string such that the sub-trees with these sub-strings as prefixes individually fit in the available memory. The algorithm breaks the input string into memory sized blocks and constructs the suffix tree in a step-wise fashion -- in each step, adding all the edges of the input string that refer to sub-strings starting within a particular block. This way, the working set size fits in the available memory.
The paper presents an approach that has the potential to have significant real-world impact. The experimental results illustrate that a 30-hour external memory suffix tree construction problem (human genome) is reduced by the introduced algorithm down to 15 minutes (a two-orders of magnitude improvement). More important, the authors provide both sequential and parallel construction algorithms and illustrate through experimentation that the proposed techniques are effective in both cases.
The paper was accepted at SIGMOD 2009, one of the premier conferences in database systems, and was nominated as one of the best papers in the conference. Moreover, the paper has received an invitation from the ACM Transactions on Database Systems (TODS) journal.
Authors and affiliation: Rajagopal Ananthanarayanan, Steven Esser, Horst Simon (Lawrence Berkeley National Laboratory), Dharmendra S. Modha -- IBM Research
Paper title: The Cat is Out of The Bag: Cortical Simulations with 10^9 neurons and 10^13 synapses
Name of journal or conference: Supercomputing 09: Proceedings of the ACM/IEEE SC2009 Conference on High Performance Networking and Computing
This paper won the prestigious 2009 ACM Gorden Bell Award. It is a "tour-de-force" in supercomputing, in the sense that it uses very large configurations of Blue Gene/P (36k nodes and 144 TB of memory) to their fullest. The computations are CPU-intensive, memory-intensive, communication-intensive, I/O-intensive and prone to load-imbalance.
Several challenges had to be addressed before this application could run at the scale and performance reported. The performance evaluation is very detailed, reporting scaling results for all modes of execution. Both weak and strong scaling are reported. In addition to measuring execution time, more detailed measurements with performance counters were also performed.
The scientific result is unprecedented. The authors were the first to simulate a cortex at the scale of a cat cortex. This scale is more than an order of magnitude larger than that of any previously reported cortical simulations. The collaboration between a group of scientists with widely different backgrounds makes this work particularly attractive.
For more information concerning this article, please contact Steve Lavenberg (sslaven@us.ibm.com).
Last updated on July 27, 2010