Computer science eponyms

Computer science needs more eponyms, in the vein of Mordenkainen. Collect them all, and impress your friends! I might make a project one day of summarizing these entries, but I'd likely sell the result as a book.

• FIXME Tarjan has something like 20,004 algorithms, and all of them are outstanding

Explicitly not included in this list are: general logic (Peano and Presburger arithmetic), mathematical entities not primarily associated with computer science (Markov's inequality, Chapman-Kolmogorov equation, Young tableaux), physical theories to which computer science is merely applied (Navier-Stokes equations, Taylor-Couette flow), or statistical entities not primarily associated with computer science (Ziph's Law, Pareto efficiency). Explicitly included are: terms from computer engineering (Mead-Conway rules, Ling adders) and mathematical entities primarily associated with computer science.

UPDATE the threshold for inclusion is now: De Morgan's Laws. If you're not more computer sciency than De Morgan's Laws, you ain't gettin' in. Dank 12:25, 3 October 2011 (CDT)

• Aanderaa–Rosenberg Conjecture suggests that non-trivial monotonicity properties of undirected graphs can only be solved by Ω(N²) algorithms on N vertices (these are all evasive decision trees on all possible edges)
• Adam7 Algorithm is a 2D, 7-pass interlacing scheme optionally used by PNG due to Adam Costello
• Adleman's Theorem states that P/poly contains all problems solvable in randomized polynomial time
• Adelson-Velskii-Landis Trees are self-height-balancing binary search trees, optimizing for lookup over modification viz. red-black trees
• Aho-Corasick Algorithm extends the Knuth-Morris-Pratt automaton to match multiple strings in one pass of a text
• Akra-Bazzi Method generalizes the "master method" of Bentley, Haken, and Saxe for subproblems of significantly different size
• Amdahl's Law
• Andersen's Algorithm
• Armstrong's axioms are a set of inference rules which generate all functional dependencies of a relational database. Similarly, an Armstrong relation satisfies all the functional dependencies in the closure F⁺ (and only those dependencies).

• Backus-Naur Form
• Bajard-Kla-Muller algorithm
• Ball-Larus Heuristics
• Banerjee Inequality
• Barendregt convention
• Barendregt-Geuvers-Klop Conjecture
• Baskett, Chandy, Muntz and Palacios network
• Batcher's Odd-Even Merge
• Bayer Filter mosaics arrange RGB color filters on a square array of photosensors, and are used in a majority of single-chip image sensors. It uses twice as many green sensors as red or blue, to mimic the physiology of the human eye
• Bell-La Padula model
• Bellman-Ford Algorithm
• Beneš network
• Bentley-Ottman Algorithm
• Berlekamp-Massey Algorithm
• Berman–Hartmanis conjecture
• Bernstein chaining
• Bernstein conditions
• Biba Integrity Model
• Blinn-Phong shading
• Blom's Scheme
• Bloom filter
• Bluestein's FFT
• Blum's axioms
• Blum's Speedup Theorem
• Blum-Blum-Shub random number generator
• Boehm-Demers-Weiser garbage collector
• Booth's Algorithm
• Borůvka's Algorithm
• Bowyer-Watson Algorithm
• Boyer-Moore Algorithm
• Bremermann's Limit
• Brent's Adder
• Brent's Algorithm detects cycles using two pointers, and finds the length of the cycle directly
• Brent's Method is a hybrid root-finding algorithm combining bisection, the secant method, and inverse quadratic interpolation
• Brent's Theorem aka Brent's Law states that p < N processors can simulate N in T_p ≤ T_N + (T_1 - T_N)/p
• Bresenham's Algorithm
• Brewer's Theorem
• Brodal Queue
• Broder's Method
• Bron-Kerbosch Algorithm
• Brooks-Iyengar Algorithm
• Buchberger Algorithm
• Burrows-Wheeler Transform
• Buzen's Algorithm

• Callahan-Koblenz algorithm
• Cannon's Algorithm
• Cantor-Zassenhaus Algorithm
• Carmack's Reverse
• Chaff Algorithm
• Chaitin's algorithm
• Chaitin's Constant
• Chaitin-Briggs algorithm
• Chaitin–Kolmogorov random numbers
• Chakravala's Algorithm
• Chan's Algorithm
• Chang-Roberts Algorithm
• Cheney's Algorithm
• Chew's Second Algorithm
• Chien search
• Cholesky decomposition expands Hermitian positive-definite matrices into products of a lower triangular matrix and its conjugate transpose. solved using the Cholesky–Crout and Cholesky–Banachiewicz algorithms.
• Chomsky Hierarchy
• Chomsky Normal Form
• Chomsky-Schützenberger theorem
• Christofides Algorithm
• Church-Rosser Theorem
• Church-Turing Thesis
• Clos network
• Cobham Axioms
• Cobham's thesis
• Cocke-Younger-Kasami Algorithm
• Cohen-Sutherland algorithm
• Coffman conditions enumerate the four conditions necessary and sufficient for deadlock within a system (mutual exclusion, hold-and-wait, a lack of preemption, and circular wait)
• Commentz-Walter Algorithm
• Conway's Law
• Cook reduction
• Cook-Levin Theorem
• Cooley-Tukey Algorithm
• Coppersmith-Winograd Algorithm
• Craig, Landin and Hagersten lock
• Cranfield method
• (preconditioned) Crank–Nicolson Algorithm
• Crusader’s Convergence Algorithm

• Dadda Multiplier
• Damerau-Levenshtein distance
• Damm Algorithm
• Davis-Putnam Algorithm
• Davis-Putnam-Logemann-Loveland Algorithm
• De Bruijn presentation
• De Bruijn string
• Dekker's Algorithm
• Delaunay's Triangulation
• Dennard Scaling
• Diffie-Hellman Key Exchange
• Dijkstra's Algorithm
• Dinic's Algorithm
• DiVincenzo's criteria specify conditions necessary for a quantum computer
• Dolev's Algorithm
• Doo-Sabin subdivision surface
• Duff's Device
• Dyck Language

• Earley Parser
• Edmonds's matching algorithm constructs maximum matchings on graphs in O(|E||V|²)
• Edmonds-Karp Algorithm
• Euclid's Algorithm

• Fagin's Theorem states that the set of all properties expressible in existential second-order logic is precisely the complexity class NP
• Faugère F5 algorithm
• Fiat-Shamir Heuristic
• Fibonacci Heap
• Fisher-Yates shuffle
• Fletcher's Checksum
• Floyd's Algorithm
• Floyd-Steinberg dithering
• Flynn Taxonomy
• Ford-Fulkerson Algorithm
• Fortune's Algorithm
• Fox's Algorithm
• Fredkin gate
• Friedberg-Muchnik Theorem
• Fürer's algorithm multiplies two n-digit numbers in O(nlgn*2^O(lg*n))

• Gabbay's separation theorem
• Gabow's Algorithm
• Gal's Accurate Tables
• Gale-Church Algorithm
• Gale-Shapley algorithm
• Gilbert-Johnson-Keerthi Algorithm
• Girard's Paradox
• Girvan-Newman Algorithm
• Givens rotation
• Glushkov Automata
• Goldreich-Goldwasser-Halevi scheme
• Gomory-Hu Tree
• Gordon–Newell theorem
• Gosper's Hack
• Gosper's Hypergeometric Algorithm
• Gosper's Loop Detection Algorithm
• Gouraud shading
• Graham Scan
• Graham-Denning Model
• Gram–Schmidt process
• Gray codes
• Greibach Normal Form
• Grover's Algorithm
• Grzegorczyk hierarchy
• Guruswami-Sudan Algorithm
• Gustafson's Law
• Gutmann's Method is a 35-phase recipe for destroying data on ferromagnetic drives.
• Guttman-Rosler transform

• Hamming code
• Hamming distance
• Heckel's algorithm isolates changes between files, and is the basis for diff CACM 1978
• Hennessy-Milner Logic
• Herlihy's wait-free hierarchy
• Hirschberg's Algorithm
• Hoare logic
• Holevo's Theorem
• Holland's schema theorem
• Hong-Kung bound
• Hopcroft-Karp Algorithm
• Hopfield net
• Horn clauses
• Householder transformation
• Huet's Zipper
• Hunt-McIlroy Algorithm

• Iliffe vector
• Immerman–Szelepcsényi theorem

• Jackson network
• Jackson's theorem
• Jaro-Winkler distance
• Jefferson's Time Warp
• Jelinek-Mercer smoothing
• Jensen's Device
• Johnson's Algorithm

• Kabsch Algorithm
• Kadane's Algorithm
• Kahan Summation Algorithm
• Kannan's Theorem
• Karatsuba's Algorithm multiplies two n-digit numbers using n^log₂3 single-digit mults
• Karger's Algorithm
• Karn's algorithm extracts accurate TCP RTT measures, Karn-Partridge 1987
• Karmarkar's algorithm
• Karnaugh map
• Karp reduction
• Karp-Flatt metric
• Karp-Lipton Theorem
• Kamada-Kawai algorithm
• Kernighan-Lin algorithm
• Kirkpatrick-Seidel Algorithm
• Kleene Closure
• Kleene Plus
• Kleene Star
• Kleene–Rosser Paradox
• Kneser-Ney smoothing
• Knuth Shuffle
• Knuth-Morris-Pratt Algorithm
• Koenig Lookup
• Kohonen Algorithm
• Kohonen network
• Kolmogorov complexity
• Koomey's Law
• Kosaraju's Algorithm
• Krapchenko's Adder
• Kruskal's Algorithm
• Kryder's Law
• Kung-Leiserson systolic array
• Kuroda Normal Form

• Ladner's Theorem
• Lamport's Bakery Algorithm
• Lamport's Clock
• Lamport's Hash
• Lee-Seung algorithm
• Lehmer random number generator
• Lehmer's GCD Algorithm
• Lempel-Ziv-Welch compression
• Levenshtein automaton
• Levenshtein distance
• Levin reduction
• Liang-Barsky algorithm
• Lin-Kernighan Heuristic
• Linde-Buzo-Gray algorithm
• Ling adders
• Liskov's Substitution Principle
• Lloyd's algorithm
• Loss-DiVincenzo machines are quantum computers based off electron spin as confined to quantum dots
• Luby's algorithm
• Luhn Algorithm
• Luleå Algorithm

• Maekawa's Algorithm
• Mahaney's Theorem
• Manning algorithm
• Marzullo algorithm
• McFarling-style branch predictor
• Mead-Conway Rules
• Mealy machine
• Mellor-Crummey and Scott lock
• Merkle–Damgård construction
• The Metropolis-Hastings algorithm for MCMC obtains samples from a probability distribution that is difficult to directly sample
• Miller-Rabin Primality Test
• Minsky-Fenichel-Yochelson Algorithm
• Montgomery reduction
• Moore machine
• Moore's Law
• Morgensen-Scott encoding
• Möller-Trumbore algorithm

• Nagle's algorithm
• Nassi-Shneiderman diagram
• Needham-Schroeder Protocol
• Needleman-Wunsch Algorithm
• Neuman-Stubblebine Protocol
• Nevill-Manning algorithm
• Nick's Class
• Nisan's Generator

• Ousterhout's dichotomy/fallacy a taxonomy of systems vs scripting languages
• Otway-Rees Protocol

• Paeth-Tanaka Algorithm rotates images via a method of three shears
• Paeth Filter performs 2D image compression in PNG
• Peterson's Algorithm
• Petrick's method
• Phong shading
• Plotkin's Sticky Bit
• Pollaczek–Khinchine formula
• Pollard's Kangaroo Algorithm
• Pollard's ρ Algorithm aka Pollard's rho Algorithm factors integers in running time expected to be proportional to the square root of the smallest prime factor of the number being factored
• Popek-Goldberg virtualization requirements
• Post's correspondence problem
• Postel's Law
• Prim's Algorithm
• Proebsting's Law claims that compiler technology doubles computing power every 18 years
• Prüfer Coding
• Prüfer Sequence

• Quines
• Quine-McLuskey algorithm

• Rabin Automata
• Rabin's Information Dispersal Algorithm
• Rabin-Karp Algorithm
• Rader-Brenner Algorithm
• Radovic-Hagersten lock
• Raymond's Algorithm
• Reed-Solomon correction code
• Ricart-Agrawala Algorithm
• Rice's Theorem
• Rice-Shapiro Theorem
• Risch Algorithm
• Rivest-Shamir-Adleman Algorithm
• Rocchio's Algorithm classifies information relevance using nearest centroids
• Ruppert's Algorithm

• Sattolo's Algorithm generates a 1-cyclic derangement of an array (a permutation such that every element ends up in a new position)
• Savitch's Theorem
• Schensted Algorithm
• Schlick's approximation
• The Schönhage–Strassen algorithm multiplies two n-digit numbers in O(nlgnlglgn) bit complexity using FFTs
• Schoof's Algorithm
• Schreier-Sims Algorithm
• Schwartzian transform
• Sethi-Ullman Algorithm
• Shamir's Secret Sharing Scheme
• Shamos-Hoey Algorithm
• Shor's Algorithm
• Sipser–Lautemann theorem
• Smith's Algorithm
• Smith-Waterman algorithm
• Solomonoff-Levin distribution
• Steensgaard's Algorithm
• Stehlé-Zimmermann algorithm
• Steinhaus-Johnson-Trotter algorithm
• Strassen's Algorithm
• Suurballe's Algorithm
• Sweeney-Robertson-Tocher division algorithm

• Tarjan's Algorithm
• Tarjan's Dynamic Tree
• Tarjan's Least Common Ancestors Algorithm
• Thompson Automata
• Timsort
• Toda's theorem
• Todd–Coxeter algorithm
• Tomasulo's Algorithm
• Tonelli-Shanks Algorithm
• The Toom-Cook Algorithm multiplies two n-digit numbers using n^{log(5)/log(3)} single-digit mults
• Turing Degree
• Turing Machines

• Ukkonen's Algorithm

• Valiant-Vazirani Theorem
• Van Jacobson Channels
• Van Wijngaarden Grammars
• Verhoeff Algorithm
• Viola-Jones face detection
• Volder's algorithm
• von Neumann architecture

• Wagner-Fischer Algorithm
• Wallace Multiplier
• Wallace tree
• Warnsdorff's Algorithm
• The Williams State Machine is a common parsing automaton for DEC virtual terminal input
• Winograd's Algorithm
• Witten-Bell smoothing
• Wu's Line Algorithm
• Wu-Manber Algorithm
• Wyllie's List Ranking

• Yao's Principle
• Yeh's Algorithm

• Zhu-Takaoka Algorithm
• Zimmermann-Sassaman key-signing protocol
• Zobrist hashing