Alan Frieze

from Wikipedia, the free encyclopedia

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

Frieze studied at Oxford University (bachelor's degree in 1966) and received his doctorate in 1975 from the University of London with Keith Wolfenden. In 1968/69 he did research (as Research Officer) at British Rail and in 1969/70 he was a programmer at ICL . In 1970/71 he was a lecturer at the Polytechnic of North London and from 1972 to 1987 he taught at Queen Mary College, University of London. He has been a professor at Carnegie Mellon University since 1987 .

With Martin Dyer and Ravindran Kannan in 1991 he found a polynomial time algorithm for calculating the volumes of convex bodies in all dimensions, for which all three received the Fulkerson Prize . In addition, the work in awarding the Knuth Prize to Kannan was singled out as one of the most outstanding developments in algorithms. The running time of all previously known algorithms for volume calculation grew exponentially with the dimension. Their 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 Endre Szemerédi's regularity lemma . In their work they introduced the weak regularity lemma, which has become an important combinatorial tool for various algorithms (streaming algorithms, graph limits, sublinear algorithms).

In 1991 he received the Fulkerson Prize with Dyer and Kannan. In 1997 he was a Guggenheim Fellow . In 2014 he was selected as plenary speaker at the International Congress of Mathematicians in Seoul ( Random structures and algorithms ). He is a fellow of the American Mathematical Society .

He has been married to Carol Frieze (née Mayfield) since 1969, who also teaches computer science at Carnegie Mellon University. He has two children with her.

Web links

Individual evidence

  1. ↑ Life data according to American Men and Women of Science , Thomson Gale 2004
  2. ^ Mathematics Genealogy Project
  3. ↑ Dyer, Frieze, Kannan A random polynomial-time algorithm for approximating the volume of convex bodies , Journal of the ACM, Volume 38, 1991, pp. 1-17
  4. ↑ Frieze, Kannan The regularity lemma and approximation schemes for dense problems , Proc. 37th Symposium Foundations of Computer Science (FOCS) 1996. Frieze, Kannan A simple algorithm for constructing Szemeredis regularity partition , Electronic J. Combinatorics, Volume 6, 1999
personal data
SURNAME Frieze, Alan
ALTERNATIVE NAMES Frieze, Alan Michael (full name)
BRIEF DESCRIPTION British computer scientist
DATE OF BIRTH October 25, 1945
PLACE OF BIRTH London