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 extended 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), sparse-matrix algorithms, and fast matrix multiplication (Winograd and Coppersmith).

We are especially interested in combinatorial optimization problems. Such problems arise everywhere, from airline and steel-mill scheduling to computer-virus detection. Many problems in this area are NP-hard, making it unlikely that all instances can be solved efficiently. Therefore, we consider polynomial-time approximation algorithms, which provide solutions that are provably close to optimal. Working in collaboration with colleagues in academe, we have designed approximation algorithms for network design, scheduling, feedback vertex set, satisfiability, large cuts in graphs, and other problems. We also establish hardness bounds: levels of approximation that no polynomial-time algorithm can surpass Randomized algorithms are a powerful tool in this area, and connect naturally with the complementary approach of average-case behavior, in which typical problem instances are modeled by random structures.

Another angle is given by lower bounds on computational complexity. For example, we have proved that the element distinctness problem (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 – integer combinations of basis vectors. It is thought to be very hard to find a short or the shortest non-zero 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 the worst case. On this foundation, we built a public-key cryptosystem which, provably, is as hard to break on average as in the worst case.

Our work in cryptography includes the invention of DES (the Data Encryption Standard). We are currently working on the design of practical, private-key cryptosystems, including SEAL, a stream cipher, and MARS, a proposal for the new federal standard. (See Security on p.44.) 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 the cryptanalysis of public-key systems, an ongoing battle of wits with the systems' designers, is equally challenging.

Queuing theory studies complex communication, computer, and manufacturing systems in which messages or parts queue up while waiting to be transmitted or processed. We are studying queuing networks, whose analysis is considerably more challenging than that of isolated queues. Some problems in this area are not merely NP-complete but undecidable, and an aspect of our work is to sort out the boundaries.

Over the last few years, we have made a 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, that, more often than not, it is impossible to click your way from one random page to another.

We are working on complexity results and winner-determination heuristics for auctions and negotiations. Our results include application of the Markov Chain Monte Carlo method to combinatorial auctions and establishing hardness of approximation for several real-life variants of capacity auctions. For digital-goods auctions, where supply is unlimited, we are working to design stable auctions, encouraging bidders to bid their utility values.

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

The effort to make our research relevant is a constant. Our exposure to the real-life problems of IBM customers (and of IBM itself) is a source of motivation, both for our research direction, and for the specific problems which we focus on. Our goals are to advance the state of theoretical knowledge and to close the cycle, using our theoretical understanding to solve our customers' real-life problems.

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