Algorithms & Theory

Researchers at IBM have a distinguished history in the development of algorithms and the theory of computation in a variety of areas including foundations of complexity theory, combinatorial optimization, randomized algorithms, cryptography, streaming algorithms, search algorithms, queuing theory, online algorithms, quantum computation, communication networks, and algebraic circuit complexity.

Foundations of many types of complexity have been laid or built upon here. These include polynomial-time complexity (Cobham), algebraic complexity (Winograd), information-theoretic complexity (Chaitin), descriptive complexity (Fagin), alternating complexity (Chandra, Kozen, and Stockmeyer), parallel complexity (Pippenger), and computational complexity on the reals (Shub). We also pioneered integer programming (Gomory), the Fast Fourier Transform (Cooley), and fast matrix multiplication (Winograd and Coppersmith). One of the recent highlights is the award winning paper "Determinism versus Non-determinism for Linear-Time RAMs with Memory Restrictions" by Miklos Ajtai. Miklos Ajtai is the Knuth prize winner for 2003.

Combinatorial optimization problems arise everywhere, from airline and steel-mill scheduling to computer-virus detection. Many of these problems are NP-hard, making it unlikely that all instances can be solved efficiently. Therefore, we have focused on polynomial-time approximation algorithms, which provide solutions that are provably close to optimal. Working in collaboration with university colleagues, we have developed approximation algorithms for network design, scheduling, feedback vertex set, satisfiability, large cuts in graphs, and other problems. We have also established hardness bounds: levels of approximation that no polynomial-time algorithm can surpass. Integer programming is another optimization tool with immense practical utility; we are leading proponents of the theory and practice of integer programming, and we make some of our tools available through the open-source initiative COIN.

Other useful tools we employ include randomized algorithms, which are often simpler or more efficient than deterministic ones, and random structures, which provide a framework for modeling typical problem instances. We also work in the area of lower bounds on computational complexity. For example, we have proved that the element distinctness problem - that is, testing whether a database has two identical entries - cannot be solved in linear time under a realistic computational model limited only by working memory that is slightly smaller than the input size.

Our work in cryptography includes the invention of DES (the Data Encryption Standard), and recent private-key cryptosystems including SEAL, a stream cipher. We have more theoretically oriented work on public-key systems, including attacks on discrete logarithms in fields of characteristic two, lattice-based attacks on some RSA variants, and integer factorization. The private-key work, particularly, has direct application to IBM products, but we also relish the challenge of cryptanalyzing public-key systems, breaking systems designed to be unbreakable.

Over the last few years, we have made serious study of the World Wide Web. Our Clever search engine uses matrix-spectral techniques to find "authorities" and "hubs" on the Web, and we have found new ways to cluster hypertext documents and label the clusters. We have also reached surprising conclusions about the huge directed graph the Web comprises: for example, more often than not, it is impossible to click your way from one random page to another. We are contributing to IBM's e-business software, including algorithms for Internet auctions and the use of knowledge discovery and data mining techniques for personalization of online commerce.

In an ongoing effort to make our research relevant, we actively seek out real-life problems of IBM customers and of IBM itself, both for our broad research direction and for specific problems on which we focus. Our goals are to advance the state of theoretical knowledge and to "close the cycle," using theoretical understanding to help solve our customers' problems.

Recent Accomplishments

Miklos Ajtai received the Knuth prize for 2003 and delivered a plenary lecture at STOC 2003 conference.

D. Williamson gave a plenary talk "Finding Provably Near-Optimal Solutions to Discrete Optimization Problems", at 16th Cumberland Conference on Combinatorics, Graph Theory, and Computing, May 2003, at SIAM 50th Anniversary Meeting, Philadelphia, PA, July 2002 (invited semi-plenary talk) and SIAM Conference on Discrete Mathematics, San Diego, CA, August 2002 (invited plenary talk).

Don Coppersmith received RSA award in 2002. He is scheduled to give the IACR Distinguished Lecture at the Asiacrypt 2003 conference in Taipei, Taiwan.

Jonathan Lee's book "A First Course in Combinatorial Optimization", Cambridge University Press, will appear in February 2004.

R. Fagin delivered a Distinguished Lecture "Optimal aggregation algorithms for middleware", at University of Toronto, Toronto, Canada, October 2002.

N. Megiddo received the IBM Invention Achievement Award, 12th Plateau, June 2003.

Andrei Broder, Baruch Schieber and David Williamson were invited speakers at NYU Theory Days and Columbia Optimization Days in 2001-2003.

Baruch Schieber is named to the executive board of DIMACS and Brenda Dietrich is named to the advisory board of DIMACS.

Rate from		low...		to	...high
Usefulness: