IBM Research authors around the world submitted 132 papers to the 2006 Pat Goldberg Memorial Best Paper for Computer Science, Electrical Engineering and Mathematical Sciences. The quality of these papers -- published in refereed conference proceedings and journals -- was high. A committee of Professional Interest Communities (PICs) site coordinators and head of Computer Science Mark Wegman reviewed the papers and nominated 31 based on technical significance (depth and breadth) and anticipated impact on Computer Science, Electrical Engineering or Mathematical Sciences or their applications in the PIC research disciplines. The committee (see sidebar) selected four winners. In alphabetical order, they are:
A Silicon 60GHz Receiver and Transmitter Chipset for Broadband Communications
Brian Floyd (IBM), Scott Reynolds (IBM), Ullrich Pfeiffer, Troy Beukema (IBM), Janusz Grzyb, Chuck Haymes (IBM)
Digest of Technical Papers, International Solid-State Circuits Conference, San Francisco, Feb. 2006
The paper describes wireless transmitter and receiver integrated circuits that operate at the 60-GHz millimeter-wave (mmWave) band, an unlicensed band extending from 57 GHz to 66 GHz. The transmitter and receiver ICs are designed in a 0.13 um SiGe BiCMOS technology with Ft/Fmax of 200/250 GHz, and contain all the blocks needed to convert from baseband frequencies to mmWave frequencies. The circuit blocks include multiple mixers, variable gain amplifier, phase-locked loop, frequency tripler, image-rejecting filter, power amplifier, and low-noise amplifier. This level of integration on a single chip for the transmitter and a single chip for the receiver at these frequencies has not been demonstrated previously. Performance was demonstrated that is consistent with the requirements of high data rate wireless communication applications. The performance and integration levels demonstrated enable a cost-performance point that is commercially feasible for wireless consumer applications. Following the capability demonstrated in this paper, there are a number of companies engaged at various levels to commercialize this and other similar mmWave technologies. Multiple sessions are now devoted to silicon mmWave technology at the leading circuits conferences, in part due to this paper. The paper's contribution was recognized as the "ISSCC 2006 Lewis Winner Award for Outstanding Paper."
Buffer Scalability of Wireless Networks
Predrag R. Jelenkovic (Columbia University), Petar Momcilovic (University of Michigan), and Mark S. Squillante (IBM)
INFOCOM 2006
This paper derives fundamental results related to throughput in large wireless networks with finite size buffers. In a heavily cited paper by Gupta and Kumar published in 2000, it was shown that the maximum throughput per source-destination pair in a wireless network with unlimited buffer size per node is proportional to 1/N1/2 as the number of nodes N tends to infinity. Subsequently it was shown that this limiting throughput can in fact be achieved. In this paper, the authors prove that if each node has fixed finite buffer size then it is not possible to achieve this throughput limit. They then construct a protocol for wireless networks with fixed buffer size that achieves a slightly smaller throughput that is proportional to 1/(Nlog N)1/2 as N increases. The analysis involves the difficult problem of dealing with large queueing networks with finite buffers for which analytical results are very hard to obtain. The paper paves the way for more theoretical as well as practical research. Further, the paper was selected as a best paper in IEEE INFOCOM.
Cover Trees for Nearest Neighbor
Alina Beygelzimer (Watson), Sham Kakade (TTI-Chicago) and John Langford (TTI-Chicago, now Yahoo Research)
23rd International Conference on Machine Learning
This paper presents a novel data structure, called cover tree, for fast nearest neighbor operations in general metric spaces. Nearest neighbor search is a basic primitive used in many different machine learning applications. The paper gives the first algorithm which exploits the underlying structure in the problem and provably yields speed-ups when speed-ups are possible, using space that grows only linearly with the size of the data set, and with no assumptions about the problem. Cover trees enable application of powerful nearest neighbor search methods to much larger data sets than was previously possible. The paper contains experimental results that demonstrate up to several orders magnitude speed-up on large machine learning data sets. Cover trees is a breakthrough that has attracted broad academic interest and is already being taught in algorithms classes in top universities.
On the Composition of Authenticated Byzantine Agreement
Yehuda Lindell (Bar-Ilan University), Anna Lysyanskaya (Brown), Tal Rabin (IBM)
Journal of the ACM
This paper revisits an old problem and finds some surprising fundamental limitations with a wide range of implications to the field of cryptography and distributed computing. It was widely assumed that the authenticated Byzantine General's problem (reliable broadcast) will remain secure under sequential, parallel and concurrent composition, regardless of the number of adversaries. However, as the authors show, this does not hold. There is a fundamental upper bound of n/3 adversaries for parallel and concurrent composition. Even for deterministic sequential composition, there are extremely strong bounds (the authors, though, also show that there are probabilistic protocols which securely compose sequentially in the presence of more adversaries). As many higher-level protocols, e.g., in secure multi-party computation, relied on the presence of (authenticated) broadcast which are concurrently composable, this result requires revisiting a number of prior results and raises a number of interesting research questions.
Last updated August 23, 2007