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.
- 1965: Cobham's Thesis on Feasibility of the Class P
- 1966: Cooley-Tukey and Other Algorithms for Fast Fourier Transform (FFT)
- 1966: Gomory Cuts and a Lot of Early Integer Programming
- 1957: Early Automata Theory
- 1966: Lower Bound for One-Tape Turing Machine for Recognizing Palindromes
- 1968: Pumping Lemmas for Parsing
- 1970: Cocke Younger Kasami [CYK] - First N^3 algorithm for parsing ambiguous languages
- 1977: Universal Hash Functions
- 1980: Fractals - Mandelbrot Set
- 1980: Mean Value Analysis
- 1981: Alternation - Major Results in Automata Theory
- 1983: Karmarkar’s Algorithm
- 1983: Simulated Annealing
- 1988: Improvements in Interior-Point Methods
- 1990: Fastest Matrix Multiply Algorithm
- 2002: Information Complexity
- 2009: Homomorphic Encryption
- 2009: Matrix Sketching - Best Algorithms in Time and Space
- 2015: Improved Statistical Inference to Avoid Spurious Scientific Discoveries
See also Information Theory and Security for cryptography results.
BACK TO IBM RESEARCH ACCOMPLISHMENTS