Alan M. Frieze

Alan Frieze, Michael ( born October 25, 1945 in London ) is a British computer scientist.

Frieze studied at Oxford University ( BA 1966) and in 1975 received his doctorate at the University of London with Keith Wolfenden. In 1968/69 he conducted research ( as a Research Officer ) at British Rail and 1960/70 he was a programmer for ICL. 1970/71 he was a lecturer at the Polytechnic of North London and 1972 to 1987, he taught at Queen Mary College, University of London. He is at Carnegie Mellon University since 1987 professor.

With Martin Dyer and Ravindran Kannan 1991 he found a polynomial - time algorithm for computing the volumes of convex bodies in all dimensions. All three would receive for the Fulkerson price and the work was stressed during the presentation of the Knuth Prize to Kannan as one of the most significant developments of algorithms at all. The previously known algorithms for calculating the volume grew in time exponentially with the dimension. My algorithm uses Markov chain Monte Carlo algorithms ( MCMC ) and is one of the earliest and most important applications of this technique in approximation algorithms.

With Dyer, he made ​​important contributions to the probabilistic analysis of algorithms in combinatorial optimization.

With Kannan he found an algorithmic version of the regularity lemma of Szemerédi Endre. In their work, they introduced the weak regularity lemma, which was an important combinatorial tool for various algorithms (Streaming Algorithms, Graph Limits, Sublinear Algorithms ).

Received the 1991 Fulkerson Prize with Dyer and Kannan. In 1997 he was Guggenheim Fellow. He was selected as Plenarsprecher at the International Congress of Mathematicians 2014 in Seoul.

He is married since 1969 with Carol Frieze (nee Mayfield ), who also teaches computer science at Carnegie Mellon University. With her he has two children.