British mathematician
Alan M. Frieze (born 25 October 1945 in
London, England) is a professor in the Department of Mathematical Sciences at
Carnegie Mellon University,
Pittsburgh, United States. He graduated from the
University of Oxford in 1966, and obtained his PhD from the
University of London in 1975. His research interests lie in
combinatorics,
discrete optimisation and
theoretical computer science. Currently, he focuses on the probabilistic aspects of these areas; in particular, the study of the asymptotic properties of
random graphs, the average case analysis of algorithms, and
randomised algorithms. His recent work has included
approximate counting and volume computation via
random walks; finding edge disjoint paths in
expander graphs, and exploring
anti-Ramsey theory and the stability of
routing algorithms.
Key contributions
Two key contributions made by Alan Frieze are:
(1) polynomial time algorithm for approximating the volume of
convex bodies
(2) algorithmic version for
Szemerédi regularity lemma
Both these algorithms will be described briefly here.
Polynomial time algorithm for approximating the volume of convex bodies
The paper
[1]
is a joint work by
Martin Dyer, Alan Frieze and
Ravindran Kannan.
The main result of the paper is a randomised algorithm for finding an approximation to the volume of a convex body in -dimensional Euclidean space by assume the existence of a membership oracle. The algorithm takes time bounded by a polynomial in , the dimension of and .
The algorithm is a sophisticated usage of the so-called
Markov chain Monte Carlo (MCMC) method.
The basic scheme of the algorithm is a nearly uniform sampling from within by placing a grid consisting n-dimensional cubes and doing a random walk over these cubes. By using the theory of
rapidly mixing Markov chains, they show that it takes a polynomial time for the random walk to settle down to being a nearly uniform distribution.
Algorithmic version for Szemerédi regularity partition
This paper
[2]
is a combined work by Alan Frieze and
Ravindran Kannan. They use two lemmas to derive the algorithmic version of the
Szemerédi regularity lemma to find an -regular partition.
Lemma 1:
Fix k and and let be a graph with vertices. Let be an equitable partition of in classes . Assume and . Given proofs that more than pairs are not -regular, it is possible to find in O(n) time an equitable partition (which is a refinement of ) into classes, with an exceptional class of cardinality at most and such that
Lemma 2:
Let be a matrix with , and and be a positive real.
(a) If there exist , such that , and then
(b) If , then there exist , such that , and where . Furthermore, , can be constructed in polynomial time.
These two lemmas are combined in the following algorithmic construction of the
Szemerédi regularity lemma.
[Step 1] Arbitrarily divide the vertices of into an equitable partition with classes where and hence . denote .
[Step 2] For every pair of , compute . If the pair are not regular then by Lemma 2 we obtain a proof that they are not regular.
[Step 3] If there are at most pairs that produce proofs of non regularity that halt. is regular.
[Step 4] Apply Lemma 1 where , , and obtain with classes
[Step 5] Let , , and go to Step 2.
Awards and honours
- In 1991, Frieze received (jointly with
Martin Dyer and
Ravi Kannan) the
Fulkerson Prize in Discrete Mathematics awarded by the
American Mathematical Society and the
Mathematical Programming Society. The award was for the paper "A random polynomial time algorithm for approximating the volume of convex bodies" in the Journal of the ACM).
- In 1997 he was a Guggenheim Fellow.
- In 2000, he received the IBM Faculty Partnership Award.
- In 2006 he jointly received (with
Michael Krivelevich) the Professor Pazy Memorial Research Award from the United States-Israel Binational Science Foundation.
- In 2011 he was selected as a SIAM Fellow.
[3]
- In 2012 he was selected as an AMS Fellow.
[4]
- In 2014 he gave a
plenary talk at the International Congress of Mathematicians in Seoul, South Korea.
- In 2015 he was selected as a Simons Fellow.
- In 2017 he was promoted to University professor.
- In 2022 he became the Orion Hoch, S 1952 Professor.
Personal life
Frieze is married to
Carol Frieze, who directs two outreach efforts for the computer science department at Carnegie Mellon University.
[5]
References
External links
|
---|
International | |
---|
National | |
---|
Academics | |
---|
Other | |
---|