Mathematics       


Programs are mathematical objects that need study. Using the tools of mathematics, we can understand the fundamentals of what is computable and how fast functions can be computed.

  1. 1965:  Cobham's Thesis on Feasibility of the Class P
  2. 1966:  Cooley-Tukey and Other Algorithms for Fast Fourier Transform (FFT)
  3. 1966:  Gomory Cuts and a Lot of Early Integer Programming
  4. 1957:  Early Automata Theory
  5. 1966:  Lower Bound for One-Tape Turing Machine for Recognizing Palindromes
  6. 1968:  Pumping Lemmas for Parsing
  7. 1970:  Cocke Younger Kasami [CYK] - First N^3 algorithm for parsing ambiguous languages
  8. 1977:  Universal Hash Functions
  9. 1980:  Fractals - Mandelbrot Set
  10. 1980:  Mean Value Analysis
  11. 1981:  Alternation - Major Results in Automata Theory
  12. 1983:  Karmarkar’s Algorithm
  13. 1983:  Simulated Annealing
  14. 1988:  Improvements in Interior-Point Methods
  15. 1990:  Fastest Matrix Multiply Algorithm
  16. 2002:  Information Complexity
  17. 2009:  Homomorphic Encryption
  18. 2009:  Matrix Sketching - Best Algorithms in Time and Space
  19. 2015:  Improved Statistical Inference to Avoid Spurious Scientific Discoveries

See also Information Theory and Security for cryptography results.

BACK TO IBM RESEARCH ACCOMPLISHMENTS