| layout | title | description | header-img |
|---|---|---|---|
page |
Algorithms |
just a list |
img/people.jpg |
This page is a compilation of the list of top algorithms tweeted here.
Disclaimers:
- It is not intended to be a definitive list. To add a name to the list, drop me an email or do a pull request.
- Credits are not intended to be complete, I often just put a single name but many algorithms have a much more complicated history (you can check the associated link for more details).
- "Algorithm" should be understood in a loose sense and it includes mathematical models (eg. least squares, lasso, SVM, etc.) that can be solved using different algorithms (but these concepts were key conceptual breakthroughs which often drove algorithmic research).
- The classification is rather arbitrary, since many algorithms belong to several classes.
- 1895: TDMA (Guglielmo Marconi)
- 1941: CDMA (Hedy Lamarr, George Antheil)
- 1948: Information theory (Claude Shannon)
- 1950: Hamming codes (Richard Hamming)
- 1952: Huffman coding (David Huffman)
- 1955: Convolutional codes (Peter Elias)
- 1960: Reed-Solomon codes (Irving Reed, Gustave Solomon)
- 1960: Low-density parity check codes (Robert Gallager)
- 1976: Arithmetic coding (Jorma Rissanen)
- 1977: Lempel–Ziv–Markov (Abraham Lempel, Jacob Ziv)
- 1978: Diffie Hellman key exchange (Ralph Merkle)
- 1978: RSA (Ron Rivest, Adi Shamir, Leonard Adleman)
- 1979: Block Truncation Coding (Edward J. Delp, O.R. Mitchel)
- 1985: Elliptic-curve cryptography (Neal Koblitz, Victor Mille)
- 1991: Turbo code (Claude Berrou)
- 1993: Embedded Zerotrees of Wavelet transforms (J. Shapiro)
- 1994: Shor's Algorithm (Peter Shor)
- 1996: Set partitioning in hierarchical trees (Amir Said, William Pearlman)
- 1996: Lattice based cryptography (Miklós Ajtai)
- 2000: JPEG2K (David Taubman)
- 2002: Polar codes (Norbert Stolte, Erdal Arıkan)
- 300 BC: Euclid GCD (Euclid)
- 600 AD: Chinese Remainder algorithm (Aryabhata)
- 1795: Prony (Gaspard Riche de Prony)
- 1956: Gröbner basis (Bruno Buchberger)
- 1975: Pollard's rho integer factorization (John Pollard)
- 1976: Miller-Rabin primality test (Gary Miller, Michael O. Rabin )
- 1982: LLL (Arjen Lenstra, Hendrik Lenstra, László Lovász)
- 2000: Lasserre's hierarchy (Jean-Bernard Lasserre, Pablo Parillo)
- 2002: AKS primality test (Manindra Agrawal, Neeraj Kayal, Nitin Saxena)
- 1880: Depth-first search (Charles Pierre Trémaux)
- 1887: Radix sort (Herman Hollerith)
- 1930: Prim minimum spanning tree (Vojtěch Jarník, Robert Prim)
- 1945: Breadth-first search (Konrad Zuse, Michael Burke)
- 1953: Hashing (Hans Peter Luhn)
- 1953: Katz Centrality (Leo Katz)
- 1954: Dynamic programming (Richard Bellman)
- 1956: Dijkstra (Edsger Dijkstra)
- 1956: Kruskal minimum-spanning-tree (Joseph Kruskal)
- 1956: Bellman-Ford shortest paths (Richard Bellman, Lester Ford)
- 1959: Quicksort (Tony Hoare)
- 1962: Topological sorting (Arthur Kahn)
- 1962: Floyd–Warshall all pairs shortest path (Robert Floyd, Stephen Warshall)
- 1963: Planar graph embedding (William Tutte)
- 1964: Steinhaus-Johnson-Trotter permutation generation (Hugo Steinhaus, Selmer M. Johnson, Hale F. Trotter)
- 1968: A star shortest path (Peter Hart, Nils Nilsson, Bertram Raphael )
- 1970: Knuth-Morris-Pratt string search (Donald Knuth, Vaughan Pratt, James H. Morris)
- 1970: Needleman-Wunsch dynamic programming (Saul Needleman, Christian Wunsch)
- 1972: Tarjan stronly connected components (Robert Tarjan)
- 1977: Boyer-Moore string search ( Robert S. Boyer, Strother Moore)
- 1984: Maximum subarray problem (Jay Kadane)
- 1999: Locality sensitive hashing (Piotr Indyk)
- 2000: Dancing links (Donald Knuth)
- 2002: Girvan-Newman communities detection (Michelle Girvan, Mark Newman)
- 2004: Chaitin graph coloring (Gregory Chaitin)
- 2008: MapReduce (Jeffrey Dean, Sanjay Ghemawat)
- 1814: Gauss quadrature (Carl Friedrich Gauss)
- 1895: Runge Kutta (Carl David Tolme Runge, Martin Wilhelm Kutta)
- 1911: Richardson extrapolation (Lewis Fry Richardson)
- 1928: Finite differences (Richard Courant, Kurt Friedrichs, Hans Lewy)
- 1943: Finite elements (Richard Courant)
- 1959: Finite volume method (Sergei Godunov)
- 1971: Spectral methods (Steve Orszag, David Gottlieb)
- 1976: Multigrid method (Achi Brandt, Wolfgang Hackbusch)
- 1987: Fast Multipole Method (Vladimir Rokhlin, Leslie Greengard)
- 1990: Symplectic integration (Haruo Yoshida)
- 1996: Fast marching method (James Sethian)
- 1795: Least-squares fitting (Carl Friedrich Gauss, Adrien-Marie Legendre)
- 1910: Cholesky decomposition (André-Louis Cholesky)
- 1938: LU decomposition (Tadeusz Banachiewicz)
- 1952: Conjugate gradient (Cornelius Lanczos, Magnus Hestenes, Eduard Stiefel)
- 1957: Minimum degree sparse matrix reordering (Harry Markowitz)
- 1961: QR algorithm (V. N. Kublanovskaya, J. G. F. Francis)
- 1964: Sinkhorn (Richard Sinkhorn)
- 1965: Golub-Reinsch SVD (Gene Golub)
- 1969: Sparse matrix ordering (Elizabeth Cuthill, James McKee)
- 1969: Strassen matrix multiplication (Volker Strassen)
- 1977: Incomplete LU factorization (Henk van der Vorst)
- 1986: GMRES/BiCGSTAB (Youcef Saad, Henk van der Vorst)
- 1990: Coppersmith-Winograd (Don Coppersmith, Shmuel Winograd)
- 1996: PageRank (Larry Page, Sergey Brin)
- 1999: Hierarchical matrix (Wolfgang Hackbusch)
- 1960: B-Splines (Pierre Bezier, Paul de Faget de Casteljau)
- 1968: Ray tracing (Appel A.)
- 1969: Binary space partitioning (Robert Schumacker)
- 1969: Non-uniform rational B-spline (Ken Versprille)
- 1971: de Boor's algorithm (Carl de Boor)
- 1972: Newell's painter algorithm (Martin Newell, Dick Newell, Tom Sancha)
- 1972: Graham scan convex hull (Ronald Graham)
- 1974: Sutherland-Hodgman polygons clipping (Ivan Sutherland, Gary Hodgman)
- 1974: Z buffer (Wolfgang Straßer)
- 1975: k-d tree nearest neighbor search (J. L. Bentley)
- 1976: Floyd–Steinberg dithering (Robert Floyd, Louis Steinberg)
- 1978: Catmull–Clark Subdivision Surfaces (Edwin Catmull, Jim Clark)
- 1981: Bowyer–Watson Delaunay triangulation (Adrian Bowyer, David Watson)
- 1983: Perlin noise (Ken Perlin)
- 1983: Alpha shapes (Herbert Edelsbrunner)
- 1988: Semi-discrete optimal transport (V. I. Oliker and L. D. Prussner)
- 1987: Marching cubes (William Lorensen, Harvey Cline)
- 1993: Delaunay refinement (Ruppert, Chew)
- 1996: Progressive meshes (Hugues Hoppe)
- 1996: Path tracing (E. Lafortune)
- 1997: Metropolis light transport (Eric Veach, Leonidas Guibas)
- 2001: Photon mapping (Henrik Wann Jensen)
- 1964: Mathematical morphology (Georges Matheron, Jean Serra)
- 1965: Fast Fourier transform (John Tukey, James Cooley)
- 1972: Gerchberg-Saxton phase retrieval (R. W. Gerchberg and W. O. Saxton)
- 1978: Discrete Cosine Transform (Narasimha, M.; Peterson, A.)
- 1977: MUSIC frequency estimation (R.O Schmidt)
- 1986: Canny edge detector (John Canny)
- 1987: Anisotropic diffusion (Pietro Perona, Jitendra Malik)
- 1988: Orthogonal Wavelets (Ingrid Daubechies)
- 1989: Fast wavelet transform (Stéphane Mallat)
- 1989: ESPRIT frequency estimation (R. Roy and T. Kailath)
- 1989: Mumford-Shah segmentation (David Mumford, Jayant Shah)
- 1990: Matrix pencil frequency estimation (Y. Hua and T. K. Sarkar)
- 1992: Approximate recursive filtering (Rachid Deriche)
- 1992: Total variation denoising (L. I. Rudin, S. Osher, E. Fatemi)
- 1993: Matching pursuit (Stéphane Mallat)
- 1997: Lifting scheme (Wim Sweldens)
- 1998: Basis pursuit (David Donoho)
- 1999: FastICA (Aapo Hyvärinen)
- 2004: SIFT (David Lowe)
- 2005: Non-local means (Antoni Buades, Jean-Michel Morel)
- 2006: Compressed sensing (Emmanuel Candes)
- 2007: Block-matching and 3D filtering (Kostadin Dabov, Alessandro Foi, Vladimir Katkovnik, Karen Egiazarian)
- 2011: Phase lift phase retrieval (Emmanuel Candes, Thomas Strohmer, Vladislav Voroninski)
- 2013: Blasso sparse spikes superresolution (Yohann de Castro)
- 1901: Principal component analysis (Karl Pearson)
- 1912: Maximum likelihood estimation (Ronald Fisher)
- 1943: Ridge regression (Andrey Tikhonov)
- 1956: Kernel density estimation (Emanuel Parzen, Murray Rosenblatt)
- 1957: K-means / Lloyd-max (Stuart Lloyd)
- 1958: Logistic regression (David Cox)
- 1960: Empirical risk minimization (Vladimir Vapnik)
- 1962: k-nearest neighbor (George Sebestyen)
- 1963: Support vector machine (Vladimir Vapnik)
- 1966: Hidden Markov model (Leonard Baum)
- 1966: Baum-Welch HMM MLE (Leonard Baum, Lloyd Welch)
- 1968: K-fold cross validation (John Tukey)
- 1981: RANSAC parameter estimation (Martin Fischler, Robert Bolles)
- 1982: Recurrent neural network (John Hopfield)
- 1984: Approximate Bayesian Computation (Peter Diggle, Richard Gratton)
- 1984: Classification And Regression Tree (Leo Breiman, J. H. Friedman, R. A. Olshen, C. J. Stone)
- 1984: Probably approximately correct learning (Leslie Valiant)
- 1990: Boosting (Robert Schapire)
- 1990: Convolutional neural network (Yann LeCun)
- 1990: Spectral clustering (A. Pothen, H. Simon, K.-P. Liou)
- 1994: Bootstrap (Leo Breiman)
- 1995: Random forests (Leo Breiman)
- 1995: Kernel trick for SVM (Corinna Cortes, Vladimir Vapnik)
- 1996: Lasso (Robert Tibshirani)
- 1996: DBSCAN clustering (Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu)
- 1997: Long short-term memory (Sepp Hochreiter, Jürgen Schmidhuber)
- 2001: Aggregating algorithm (Volodya Vovk)
- 2003: Latent Dirichlet Allocation (Blei, David M.; Ng, Andrew, Michael Jordan)
- 2012: Dropout (Geoffrey Hinton et al)
- 2014: Generative adversarial networks (Ian Goodfellow)
- 1949: Metropolis–Hastings (Stanislaw Ulam, Nicholas Metropolis, John von Neumann)
- 1955: Importance sampling (Herman Kahn)
- 1960: Kalman filter (Rudolf Kálmán)
- 1967: Max product message passing (Andrew Viterbi)
- 1967: Sobol low-discrepancy sequences (Ilya Sobol)
- 1974: Milstein method (Grigori Milstein)
- 1974: Alias method (Alastair Walker)
- 1977: Expectation Maximization (Arthur Dempster, Nan Laird, Donald Rubin)
- 1978: VEGAS Monte-Carlo (G.P. Lepage)
- 1982: Sum product message passing, belief propagation) (Judea Pearl)
- 1984: Gibbs sampling (Stuart and Donald Geman)
- 1985: Reservoir sampling (Jeffrey Vitter)
- 1987: Hamiltonian Monte Carlo (Simon Duane)
- 1990: Junction tree for message passing (P. Shafer, G. Shenoy)
- 1996: Particle filter (Neil Gordon, David Salmond, Adrian Smith)
- 1996: Coupling from the past (James Propp, David Wilson)
- 1997: Mersenne twister for random number generation (Makoto Matsumoto, Takuji Nishimura)
- 2004: Nested-sampling (John Skilling)
- 2012: Tamed Euler method (Martin Hutzenthaler)
- 1669: Newton’s Method (Isaac Newton)
- 1847: Steepest descent (Augustin-Louis Cauchy)
- 1939: Linear programming (Leonid Kantorovich)
- 1944: Levenberg-Marquardt ( Kenneth Levenberg, Donald Marquardt)
- 1947: Simplex (George Dantzig)
- 1952: Stochastic gradient descent (Herbert Robbins, Sutton Monro, Jacob Wolfowitz, Jack Kiefer)
- 1956: Ford-Fulkerson maximum flow (L. R. Ford, D. R. Fulkerson)
- 1956: Frank-Wolfe (Marguerite Frank, Philip Wolfe)
- 1957: Hungarian (Harold Kuhn, James Munkres)
- 1958: Cutting-plane mixed integer programming (Ralph Gomory)
- 1960: Branch and bound for combinatorial optimization (A. H. Land, A. G. Doig)
- 1962: Gale-Shapley stable marriage (David Gale, Lloyd Shapley)
- 1964: Powell's method (Michael Powell)
- 1965: Nelder–Mead derivative free method (John Nelder, Roger Mead)
- 1967: Bregman iterative projections (Lev Bregman)
- 1970: Proximal point algorithm (Tyrrell Rockafellar)
- 1970: Reverse mode automatic differentiation (Seppo Linnainmaa)
- 1970: BFGS (Charles George Broyden, Roger Fletcher, Donald Goldfarb and David Shanno)
- 1970: Majorize-Minimize (J.M. Ortega, W.C. Rheinboldt)
- 1970: Edmonds–Karp max-flow (Yefim Dinitz, Jack Edmonds, Richard Karp)
- 1973: Genetic algorithm (Ingo Rechenberg, Hans-Paul Schwefel)
- 1975: Alternating direction method of multipliers (R. Glowinski, A. Marrocco, D. Gabay, B. Mercier)
- 1979: Mirror descent (Arkadi Nemirovski)
- 1979: [Auctions](Auction algorithm) (Dimitri Bertsekas)
- 1979: Forward-Backward (Pierre-Louis Lions, Bertrand Mercier)
- 1979: Douglas-Rachford (Pierre-Louis Lions, Bertrand Mercier)
- 1983: Fast gradient method (Yurii Nesterov)
- 1983: Simulated Annealing (Scott Kirkpatrick)
- 1984: Interior point method (Narendra Karmarkar)
- 1984: Espresso minimization algorithm (Robert Brayton)
- 1986: Push-relabel maximum flow (Andrew V. Goldberg, Robert Tarjan)
- 1986: Dykstra (Richard Dykstra)
- 1994: Dynamic time warping (D. J. Berndt, J. Clifford)
- 1995: Network simplex (James Orlin, Robert Tarjan)
- 1995: Maxcut SDP relaxation (Michel Goemans, David Williamson)
- 1995: alphaBB for global optimization (Ioannis Androulakis)
- 1996: Conflict driven clause learning (Marques-Silva and Sakallah)
- 2001: Burrer-Montero (Samuel Burer, Renato Monteiro)