IBM Research authors around the world submitted over 145 papers to the 2008 Pat Goldberg Memorial Best Paper Competition for Computer Science, Electrical Engineering and Mathematical Sciences.
The quality of these papers -- published in refereed conference proceedings and journals -- was high. The Professional Interest Communities (PICs) nominated 36 of these for best paper consideration. A committee of PIC site coordinators and head of Computer Science Mark Wegman reviewed the nominated papers and evaluated them based on technical significance (depth and breadth) and anticipated impact on Computer Science, Electrical Engineering or Mathematical Sciences or on their applications in the PIC research disciplines.
The committee (see sidebar) selected four winners. In alphabetical order by title, they are:
Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization: Authors: Jacob Abernethy (UC Berkeley), Elad Hazan (IBM Almaden), Alexander Rakhlin (UC Berkeley)
Summary: Bandit linear optimization is a fundamental problem in iterated decision making under uncertainty. It is a natural generalization of the well-known multi-armed bandit problem to convex optimization, formalizing a host of practical decision problems. The standard measure of performance of an online algorithm is its regret, or the difference between the algorithm's payoff and the payoff of the best fixed decision in hindsight. Existing algorithms for bandit linear optimization were either inefficient or had a sub-optimal regret bound, and the existence of an efficient optimal algorithm was considered an important open question. This paper resolves this question by giving an algorithm which runs in polynomial time and achieves the optimal O(T^{1/2}) regret, where T is the number of rounds. The main novel technique is the introduction of "barrier functions" from convex optimization. The paper analyses a new property of these functions, and shows that they optimally characterize the exploration-exploitation tradeoff in bandit problems. This paper won the Machine Learning Journal award for the best student-co-authored paper in the conference. Read the paper (pdf)
MCDB: A Monte Carlo Approach to Managing Uncertain Data: Authors: Ravi Jampani (U. Florida), Fei Xu (U. Florida), Mingxi Wu (U. Florida), Luis Leopoldo Perez (U. Florida), Christopher Jermaine (U. Florida), Peter Haas (IBM Almaden)
Summary: This paper presents a novel system for managing uncertain data based on Monte Carlo simulations. Unlike existing probabilistic databases that require explicit attribute-level or tuple-level probabilities, the proposed system abstracts uncertainty using pseudo-randomly generated values for uncertain attributes. The generated values are parameterized allowing for what-if scenarios. The main contributions is that (a) by managing parameters instead of explicit probabilities and (b) by estimating rather than exactly computing the probability distribution over possible query answers, many limitations of prior systems are eliminated. Most importantly, the proposed system handles gracefully arbitrary joint-probability distribution over discrete and continuous attributes, complex queries as well as arbitrary functionals like means and quantiles. In contrast to earlier prior work on probabilistic databases which has focused on how to restrict their functionality in order to guarantee performance, MCDB starts from a powerful functionality, and proposes a entirely new class of non-trivial optimizations to improve performance. As a result, this seminal work has the potential to facilitate real-wold risk assessment and decision-making by performing large scale statistical inferencing, which is a crucial problem for modern enterprises.Read the paper (ACM portal)
Portably Solving File TOCTTOU Races with Hardness Amplification: Authors: Dan Tsafrir (IBM Watson), Tomer Hertz (Microsoft Research), David Wagner (UC Berkeley), Dilma Da Silva (IBM Watson)
Summary: The association between a file's name and the underlying file object is, by design, mutable (namely, it can be changed). This mutability has been the source of endless trouble during the past two decades, because it creates a "time-of-check-to-time-of-use" (TOCTTOU) race condition that constitutes a serious software vulnerability. The gist of the problem is the following programming idiom: using a file's name, an application checks something regarding the file, and then, depending on the result of the check, the application conditionally applies some followup operation to the file, unjustifiably assuming that the result of the check hasn't changed. Malicious attackers can exploit this idiom by changing the association between the file's name and underlying file object (just after the check and just before the operation) in a way that allows them to gain unlawful control over the system. Due to its overwhelming prevalence in software, the TOCTTOU issue gained a status of a classical problem, and very many research studies have attempted to solve it. But all of the suggested solutions required intrusive changes to existing systems, making them inapplicable in practice for most environments. Thus, despite all the work, dozens of TOCTTOU bugs are being discovered every year in mainstream applications under all operating systems. (These statistics are based on the U.S. National Vulnerabilities Database.)
The solution presented in this paper is elegant, surprisingly simple, and has the appealing quality of "how come no one has thought of that before". Specifically, by doing user-mode path resolution, the authors allow programmers to easily and conveniently turn a vulnerable check-use pair of file operations into an atomic transaction that cannot be exploited. Importantly, the proposed mechanism is standard-confirming and immediately applicable within existing systems. The proposed mechanism is generic and can be used to implement a wide verity of arbitrary security/management policies, which would otherwise mandate an intrusive (and thus typically inapplicable) system change. The mechanism consequently opens up intriguing possibilities for further research. It was chosen as one of two best papers at FAST. Read the paper (pdf)
Quantum Communication with Zero Capacity Channels: Authors: Graeme Smith (IBM Watson), Jon Yard (Los Alamos National Labs)
Summary: Analogous to classical information theory, communication over a noisy quantum channel has been an active area of study in quantum computing. A fundamental bound on quantum error correction is "quantum capacity", which quantifies the amount of quantum data that can be protected. Smith and Yard show a startling result: two quantum channels, each with zero quantum capacity, can have a positive capacity when used together. This result, while simple to describe, has been generated a lot of excitement and has been published in the prestigious Science journal. Their result provides some significant clues towards the deep structure of quantum communication. In particular, quantum capacity does not completely specify a channel's ability to transmit quantum information. A perspective of the paper along with an explanation of the result can be found in Science. Read the paper
For more information concerning this article, please contact Steve Lavenberg (sslaven@us.ibm.com).