Name Alan Frieze | Role Professor | |
![]() | ||
Awards Fulkerson Prize, Guggenheim Fellowship for Natural Sciences, US & Canada |
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.
Contents
- Key contributions
- Polynomial time algorithm for approximating the volume of convex bodies
- Algorithmic version for Szemerdi regularity partition
- Awards and honours
- References
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 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
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
Algorithmic version for Szemerédi regularity partition
This paper 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
Lemma 1:
Fix k and
Lemma 2:
Let
(a) If there exist
(b) If
These two lemmas are combined in the following algorithmic construction of the Szemerédi regularity lemma.
[Step 1] Arbitrarily divide the vertices of
[Step 2] For every pair
[Step 3] If there are at most
[Step 4] Apply Lemma 1 where
[Step 5] Let