IBM Research has a distinguished history in the development of algorithms and the theory of computation. 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).

Our areas of current activity are described below; more information on particular projects can be found at www.research.ibm.com/compsci/algorithms/.

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.

One of our widely recognized recent results is in the theory of lattices, that is, integer combinations of basis vectors. It is thought to be very hard to find a short or the shortest nonzero vector in a lattice, a problem that has been open for 150 years. We showed how to generate a lattice at random, in such a way that the average-case hardness of finding a short vector is as bad as in the worst case. On this foundation, we built a public-key cryptosystem that, provably, is as hard to break on average as the worst case.

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 (see KDD on page 30) for personalization of online commerce.

Queuing theory, online algorithms, quantum computation, communication networks, and algebraic circuit complexity are other areas in which we work.

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.

Please contact Paridhi Verma to obtain copies of the Computer Science Brochure