From Wikipedia, the free encyclopedia
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.
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[edit]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 ϵ {\displaystyle \epsilon } approximation to the volume of a convex body K {\displaystyle K} in n {\displaystyle n} -dimensional Euclidean space by assume the existence of a membership oracle. The algorithm takes time bounded by a polynomial in n {\displaystyle n} , the dimension of K {\displaystyle K} and 1 / ϵ {\displaystyle 1/\epsilon } .
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 K {\displaystyle K} 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[edit]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 ϵ {\displaystyle \epsilon } -regular partition.
Lemma 1:
Fix k and γ {\displaystyle \gamma } and let G = ( V , E ) {\displaystyle G=(V,E)} be a graph with n {\displaystyle n} vertices. Let P {\displaystyle P} be an equitable partition of V {\displaystyle V} in classes V 0 , V 1 , … , V k {\displaystyle V_{0},V_{1},\ldots ,V_{k}} . Assume | V 1 | > 4 2 k {\displaystyle |V_{1}|>4^{2k}} and 4 k > 600 γ 2 {\displaystyle 4^{k}>600\gamma ^{2}} . Given proofs that more than γ k 2 {\displaystyle \gamma k^{2}} pairs ( V r , V s ) {\displaystyle (V_{r},V_{s})} are not γ {\displaystyle \gamma } -regular, it is possible to find in O(n) time an equitable partition P ′ {\displaystyle P'} (which is a refinement of P {\displaystyle P} ) into 1 + k 4 k {\displaystyle 1+k4^{k}} classes, with an exceptional class of cardinality at most | V 0 | + n / 4 k {\displaystyle |V_{0}|+n/4^{k}} and such that ind ( P ′ ) ≥ ind ( P ) + γ 5 / 20 {\displaystyle \operatorname {ind} (P')\geq \operatorname {ind} (P)+\gamma ^{5}/20}
Lemma 2:
Let W {\displaystyle W} be a R × C {\displaystyle R\times C} matrix with | R | = p {\displaystyle |R|=p} , | C | = q {\displaystyle |C|=q} and ‖ W ‖ inf ≤ 1 {\displaystyle \|W\|_{\inf }\leq 1} and γ {\displaystyle \gamma } be a positive real.
(a) If there exist S ⊆ R {\displaystyle S\subseteq R} , T ⊆ C {\displaystyle T\subseteq C} such that | S | ≥ γ p {\displaystyle |S|\geq \gamma p} , | T | ≥ γ q {\displaystyle |T|\geq \gamma q} and | W ( S , T ) | ≥ γ | S | | T | {\displaystyle |W(S,T)|\geq \gamma |S||T|} then σ 1 ( W ) ≥ γ 3 p q {\displaystyle \sigma _{1}(W)\geq \gamma ^{3}{\sqrt {pq}}}
(b) If σ 1 ( W ) ≥ γ p q {\displaystyle \sigma _{1}(W)\geq \gamma {\sqrt {pq}}} , then there exist S ⊆ R {\displaystyle S\subseteq R} , T ⊆ C {\displaystyle T\subseteq C} such that | S | ≥ γ ′ p {\displaystyle |S|\geq \gamma 'p} , | T | ≥ γ ′ q {\displaystyle |T|\geq \gamma 'q} and W ( S , T ) ≥ γ ′ | S | | T | {\displaystyle W(S,T)\geq \gamma '|S||T|} where γ ′ = γ 3 / 108 {\displaystyle \gamma '=\gamma ^{3}/108} . Furthermore, S {\displaystyle S} , T {\displaystyle T} 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 G {\displaystyle G} into an equitable partition P 1 {\displaystyle P_{1}} with classes V 0 , V 1 , … , V b {\displaystyle V_{0},V_{1},\ldots ,V_{b}} where | V i | ⌊ n / b ⌋ {\displaystyle |V_{i}|\lfloor n/b\rfloor } and hence | V 0 | < b {\displaystyle |V_{0}|<b} . denote k 1 = b {\displaystyle k_{1}=b} .
[Step 2] For every pair ( V r , V s ) {\displaystyle (V_{r},V_{s})} of P i {\displaystyle P_{i}} , compute σ 1 ( W r , s ) {\displaystyle \sigma _{1}(W_{r,s})} . If the pair ( V r , V s ) {\displaystyle (V_{r},V_{s})} are not ϵ − {\displaystyle \epsilon -} regular then by Lemma 2 we obtain a proof that they are not γ = ϵ 9 / 108 − {\displaystyle \gamma =\epsilon ^{9}/108-} regular.
[Step 3] If there are at most ϵ ( k 1 2 ) {\displaystyle \epsilon \left({\begin{array}{c}k_{1}\\2\\\end{array}}\right)} pairs that produce proofs of non γ − {\displaystyle \gamma -} regularity that halt. P i {\displaystyle P_{i}} is ϵ − {\displaystyle \epsilon -} regular.
[Step 4] Apply Lemma 1 where P = P i {\displaystyle P=P_{i}} , k = k i {\displaystyle k=k_{i}} , γ = ϵ 9 / 108 {\displaystyle \gamma =\epsilon ^{9}/108} and obtain P ′ {\displaystyle P'} with 1 + k i 4 k i {\displaystyle 1+k_{i}4^{k_{i}}} classes
[Step 5] Let k i + 1 = k i 4 k i {\displaystyle k_{i}+1=k_{i}4^{k_{i}}} , P i + 1 = P ′ {\displaystyle P_{i}+1=P'} , i = i + 1 {\displaystyle i=i+1} and go to Step 2.
Frieze is married to Carol Frieze, who directs two outreach efforts for the computer science department at Carnegie Mellon University.[5]
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4