Computer Science Hall of Fame. Curator: W.F. Klostermeyer, established 1997.
  • 1. The PCP Theorem [Arora, Babai, Sudan, et al., 1985-1992]

    • Shows that "proofs" of membership for languages in NP can be decided with high probability by examining only a constant number of bits of the specially constructed "proof." Has profound implications on hardness of approximation: problems such as clique and graph coloring have no good approximation algorithms (unles P=NP) and the MAX-SNP hard problems (e.g. Vertex Cover) do not have approximation schemes. A "tour de force of pure mathematics" and is related to the famous proof that IP=PSPACE (see for example Interactive Proofs) For more information visit PCPs and Approximation
  • 2. Cook's Theorem [NP-completeness of SAT, 1971. Independently discovered by Levin]

    • Established the existance of NP-complete sets. Karp soon showed that a host of problems were equivalent in difficulty to SAT, and thus believed intractable. Some pertinent definitions can be found in Comp.theory FAQ and some more up to date information on NP-completeness and approximation (in the style of Garey and Johnson) can be found at Compendium of NP-optimization Problems
  • 3. Halting Problem's Undecidability [Turing, 1939]

    • Showed there are problems that cannot be solved by any computer in finite time. See The Halting Problem or Halting Problem or some more information: More on TM's
  • 4. QuickSort and Average Case Analysis of QuickSort [Hoare et al.]

    • A simple elegant algorithm that is very practical. The average case analysis provides great insights into the algorithm and shows that worst-case analysis is not always the best tool. A description of the algorithm and its analysis can be found here: QuickSort
  • 5. Fast Fourier Transform Algorithm

    • O(n log n) method for Fourier transforms. Of great application in manipulation of polynomials and integer arithmetic. A description of the algorithm can be found here FFT. A beautiful use of recursion.
  • 6. Sub-cubic Matrix Multiplcation Algorithms [Strassen, Coppersmith/Winograd, et al.]

    • Strassen's original O(n^(2.81)) algorithm was faster than the obvious O(n^3) method. Current fastest in O(n^(2.37)).
  • 7. O(log n) depth sorting network [Ajtai, Komlos, & Szemeredi, 1983]

    • Fast parallel sorting. A detailed overview of parallel sorting can be found here Parallel Sorting
  • 8. Polynomial Time Linear Programming [Khachiyan, Karmarkar, 1979]

    • Visit the link Linear Programming Page
    The well-known SIMPLEX method, though practical most of the time, requires exponential time in the worst-case. These methods showed that polynomial time worst case algorithms exist, which have proved to be of great application in the design approximation algorithms. Namely:
  • 9. Semi-definite programming for approximation algorithms [Goemans and Williamson, 1994]

    • A breakthrough. Uses randomized rounding of linear programs and some deep mathematics to develop much better approximation algorithms for many NP-complete problems (e.g. MAX-CUT). You can see one of these algorithms in action here M.X. Goeman's Page Or you can visit the Semi-definite programming page Or visit David Williamson (several links here). There is a survey paper on Semi-definite programming (in general, not specifically with regard to approximation algorithms in SIAM Review, March 1996).
  • 10. Polynomial Time Algorithm for Factorization Over a Finite Field [Berlekamp]

    • Knuth called this algorithm "amazing."
  • 11a. Polynomial Time Algorithm for Determining if an integer is prime [Agarwal et al. 2002]

    • A stunning, elegant, simple (relatively speaking) algorithm. Such an algorithm had been sought, literally, for thousands of years. Though not yet as fast in practice as the randomized tests (see 11b below), as the algorithm runs is O(log^12 n) time for an integer n (though O(log^6 n) time if their conjecture proves true), a major theoretical breakthrough.
  • 11b. Randomized Primality Testing [Miller, Rabin]

    • A very fast, almost always correct, method to solve what is believed to be a very difficult (and fundamental) problem. Some basic information can be found at Miller-Rabin while the Prime Page contains useful information about primes and testing primes.
    Honorable Mention
  • a1. Competitive Analysis and Amortization Arguments(including Union-Find, Fibonacci Heaps, Paging)[Sleator, Tarjan, et al.]

    • A new method of algorithm (and data structure) analysis (based on amortization arguments). The resulting data structures (e.g. Fibonacci heaps) lead to the best known algorithms for many problems, such as Minimum Spanning Tree.
  • a2. Competitiveness of Work-Function Algorithm for k-Server Problem [Koutsoupias and Papadimitriou, 1993]

    • The tour-de-force of competitive analysis, showing the work function algorithm (folklore) is 2k-1 competitive for the k-Server problem (a generalization of the paging problem). Still conjectured to be k-competitive, however (known to be for k=2).
  • b. Relational Databases [Codd]
  • c. Edmonds Matching Algorithm [Edmonds, 1966]

    • Non-trivial algorithm for finding a maximum matching in a graph. Led to much work on graph algorithms and includes early notions of the class "P." Useful in solving other problems.
  • d. Average-Case NP-completeness [Levin, 1984].

    • Showed that some NP-complete problems are difficult in "most" instances while others are difficult only in rare instances, as described on the Average Case Complexity Page
  • e. RSA Encryption/Decryption [Rivest/Shamir/Adelman, 1978].
  • f. Other Graph Algorithms of Note:

    • -- Graph Minors [Robertson & Seymour, 1980-1990] Over a long series of papers, they show that one can test in polynomial time if H is a minor of G (H is a minor of G if H can be obtained from some subgraph of G by a series of vertex contractions).
    -- Four Color Theorem [Appel & Haken, 1976]. A corollary to the four color theorem is that any planar graph can be colored with four colors in polynomial time. See Four Color Theorem for details.
    -- Graph Isomorphism Testing. Determining if G is isomorphic to H is generally thought to be difficult, though it is not NP-complete unless the polynomial time hierarchy collapses (this result is due to Schoning and his Low Hierarchy, 1982-1988. Also follows from fact that Graph Non-isomorphism has constant-round interactive proofs). The best known algorithm for graph isomorphism requires superpolynomial time and is due to [Luks, 1982] and is deeply rooted in group theory, as is explained at Graph Isomorphism and Group Theory. Luks [JCSS, 1982] does give a polynomial time algorithm to solve the problem if vertex degrees are bounded.
    -- Maximum Flow. Original polynomial time algorithm due to Ford and Fulkerson [1962]. Current best algorithm is due to Goldberg and Tarjan: O(VE log(V^2/E) [1986].
    -- Arora's Polynomial Time Approximation Scheme for Euclidean TSP (1997-1998).
    -- Hopcroft and Tarjan's linear time planarity testing algorithm (1970)
    Honorable Mention (Early Contributions)
  • i. Euclid's GCD algorithm

    • Fast, elegant. Analysis is interesting, involving the Fibonacci numbers.
  • ii. Gaussian Elimination for Solving Linear Equations

    • Ubiquitous.
  • iii. Hamming's and Shannon's early work on codes and information theory

    • Cornerstone of modern digital communications. 
    Some Additional Links with Background Information:
    Comp.theory FAQ
    Leonid Levin's Fundamentals of Computing
    Stony Brook Algorithm Repository
    Lance Fortnow's Top Ten Complexity Theory Theorems of 1986-1996
    CMU Great CS Ideas Course
    Alternate CMU Great CS Ideas Course