Algorithms & Theory

Abstract:
This paper solves a monumental problem in complexity theory that had been considered by many researchers over a 20 year period: how to show lower bounds for computing decision problems in completely general non-uniform models of computation. In particular, this paper shows that there are problems easily solvable in polynomial time but that require linear space to be solved using any linear time non-uniform algorithm. To give an indication about how much of a breakthrough this is, consider that it was not known previously how to show that more than O(log n) space was required by any linear time algorithm. It changes the landscape of what we can prove quite dramatically. Ajtai won the 2003 Knuth Prize for what the Knuth Prize committee calls his "truly remarkable seminal contributions" to theoretical computer science, and this paper was one of the contributing factors.

"Optimal Aggregation Algorithms for Middleware" by Ron Fagin, Amnon Lotem (University of Maryland), Moni Naor (Weizmann Institute of Science)
Best Paper Award in the 2001 PODS conference.
IBM Research CS/EE/Math Best Paper for 2001.

Abstract:
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.

"Rank Aggregation Methods for the Web" by Cynthia Dwork (Microsoft), Ravi Kumar, Moni Naor (Weizmann Institute of Science), D. Sivakumar
Best paper in the Searching, Crawling and Indexing track at the 2001 World Wide Web conference.
IBM Research CS/EE/Math Best Paper for 2001.

Abstract:
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.