Over 160 papers published in conference proceedings and journals in 2001 were submitted by IBM Research authors worldwide for consideration as 2001 Computer Science/Electrical Engineering/Mathematics Best Papers. The following three were selected (in alphabetical order):
Optimal Aggregation Algorithms for Middleware
Ron Fagin, Amnon Lotem (University of Maryland), Moni Naor (Weizmann Institute of Science)
2001 ACM Symposium on Principles of Database Systems (PODS '01)
Paper Description
This paper describes how to efficiently retrieve the K objects with the highest aggregate scores from a collection of objects, each of which has m scores that are combined into a single aggregate score. The work potentially has a wide range of applications including (a) combining scores of features for multimedia data; (b) key word searching where conjunct results need to be merged; (c) meta searching on the web where results from multiple sources need to be combined; and (d) heterogeneous databases where data can come from various kinds of database systems. It is the most detailed and analytically comprehensive exposition of this problem and it substantially extends earlier influential work. In particular, the paper introduces and analyzes remarkably simple algorithms for this problem and shows them not only to be superior to existing algorithms, but to be optimal in a very strong sense. It received the Best Paper Award in the 2001 PODS conference.
Rank Aggregation Methods for the Web
Cynthia Dwork (Microsoft), Ravi Kumar, Moni Naor (Weizmann Institute of Science), D. Sivakumar
10th International World Wide Web Conference (WWW 2001)
Paper Description
The paper studies rank aggregation methods and in this context describes two ideas: (1) a formal model, Kemeny optimality, borrowed from social choice theory, as the basis for defining rank aggregation problems, and (2) a computationally efficient method, the extended Condorcet criterion, also borrowed from social choice theory, which is a natural relaxation of Kemeny optimality. The relaxation is necessary since computing Kemeny optimal orderings is shown to be NP hard, even when there are as few as 4 rankings to aggregate. An additional insight offered is an argument that Kemeny optimal orderings are hard to "spam" and that this property holds for all algorithms which satisfy the Condorcet criterion. The introduction of social choice theory into the science of searching was long overdue, and the authors make a valuable and lasting contribution in this direction. From a theoretical perspective, this paper proposes a thorough formalization and clear, intuitively motivated solution for the problem of rank aggregation in the context of the World Wide Web. This paper will doubtless lead to several practical implementation studies in the future. It was the best paper in the Searching, Crawling and Indexing track at the 2001 World Wide Web conference.
Universally Composable Security: A New Paradigm for Cryptographic Protocols
Ran Canetti
42nd Annual Symposium on Foundations of Computer Science (FOCS'01)
Paper Description
This works caps several years of efforts to devise a notion of security for cryptographic protocols, that is robust enough to withstand concurrent execution. The problem is to come up with a security notion, such that if a protocol is proved to be secure "in isolation", it would follow that concurrent executions of many instances of this protocol (with arbitrary interleaving) are also secure. This paper is the first one to come up with such a notion. It is likely that this notion will become the standard definition of (strong) security for cryptographic protocols and that this paper will become a milestone in the study of cryptographic protocols. Published in November of 2001, this work has already been cited by several other researchers (including papers in FOCS'01, STOC'02 and Eurocrypt'02) and was also covered in a recent survey on cryptographic protocols.