Algorithms and Theory       


Algorithms and Theory - History

Historic highlights


1965: Fast Fourier Transform (James W. Cooley - IBM Watson, with J. Tukey)

This work gave an O(n log n) time algorithm for computing the discrete Fourier transform on n points. This transformed signal processing and made it practical. Fast Fourier Transform is also widely used as a subroutine in many algorithms.

1977: Universal Hashing (Larry Carter, Mark Wegman - IBM Watson)

Universal hashing refers to selecting a hash function at random from a family of hash functions, in a way that guarantees a low probability of collision for any given input. This concept led to numerous practical implementations in algorithms, databases and cryptography.

1990: Fast Matrix Multiplication (Don Coppersmith, Shmuel Winograd - IBM Watson)

Following Strassen's breakthrough on matrix multiplication faster than O(n^3), Coppersmith and Winograd developed a more general framework for designing such algorithms using tensor algebra. Their algorithm, which multiplies matrices in time O(n^2.375), was the asymptotically fastest one for 20 years, until recent improvements by Stothers and Vassilevska-Williams.


1950s: Integer Programming & Cutting Planes (Ralph Gomory - IBM Watson)

Ralph Gomory was one of the founders of integer programming - solving linear programs in a way that uses only integer numbers. He proposed cutting planes as a method for solving such problems. While the idea was initially not considered practical, it later found broad applicability in conjuction with branch-and-bound methods, and today it is a fundamental component of optimization software packages.

Complexity Theory

1972: NP-Complete Problems (Richard Karp - IBM Watson)

While at IBM Watson, Richard Karp developed ways to reduce combinatorial problems to one another and thus show them to be equivalent in terms of solvability in polynomial time. These 21 problems, including Boolean Satisfiability, Integer Programming, Max Clique, Set Cover, Set Packing, Graph Coloring, and others, were later all shown to be NP-Complete (using Cook's theorem) and today they form a classical list of NP-Complete problems.


1970: Relational databases (E. F. Codd - IBM San Jose)

Relational databases are formally described and organized according to the relational model, with an algebraic relation as a basis of each data table. In the 1970s, this was a breakthrough concept which replaced earlier models and has become the predominant choice in data storage to this day.


1976: DES - Data Encryption Standard (team led by Horst Feistal - IBM Watson)

This encryption technique was developed at IBM in the 1970s and approved as a federal standard by the United States National Bureau of Standards in 1976. It is a symmetric-key block cipher which has remained in use to this day, in various forms and combinations with other encryption schemes.


1975: Fractals (Benoit Mandelbrot - IBM Watson)

Mandelbrot coined the term “fractal” to refer to a class of mathematical shapes whose uneven contours could mimic the irregularities found in nature. In 1975 he gave a mathematical definition of fractals - objects that resemble themselves at different scales of magnification. IBM computers enabled Mandelbrot to generate the images of the Mandelbrot set that have captured popular imagination.

World Wide Web

1997: Hubs and Authorities (Jon Kleinberg - IBM Almaden)

The HITS algorithm was developed by Jon Kleinberg while on leave from Cornell University at IBM Almaden. It is a link analysis algorithm that rates Web pages based on their relevance to a search query, in a recursive manner: a page has high "authority", if many "hubs" point to it, and a page is a hub if it points to many pages of high authority. This algorithm was a precursor to the PageRank algorithm that became a basis of the Google search engine.