Alan M. Frieze

Alan M. Frieze (ur. 25 października 1945 r. w Londynie , Anglia) jest profesorem na Wydziale Nauk Matematycznych Uniwersytetu Carnegie Mellon w Pittsburghu w Stanach Zjednoczonych. Ukończył Uniwersytet Oksfordzki w 1966 r., a doktorat uzyskał na Uniwersytecie Londyńskim w 1975 r. Jego zainteresowania badawcze obejmują kombinatorykę , optymalizację dyskretną i informatykę teoretyczną . Obecnie koncentruje się na problematycznych aspektach tych obszarów; w szczególności badanie właściwości asymptotycznych grafów losowych , analiza przypadków średnich algorytmów i algorytmów losowych . Jego ostatnie prace obejmowały przybliżone liczenie i obliczanie objętości poprzez błądzenie losowe ; znajdowanie rozłącznych ścieżek krawędziowych w grafach ekspandera oraz badanie teorii anty-Ramseya i stabilności algorytmów trasowania .

Kluczowe składki

Dwa kluczowe wkłady Alana Frieze to:

(1) algorytm czasu wielomianowego do aproksymacji objętości ciał wypukłych

(2) wersja algorytmiczna dla lematu o regularności Szemerédiego

Oba te algorytmy zostaną tutaj pokrótce opisane.

Algorytm czasu wielomianowego do aproksymacji objętości ciał wypukłych

Artykuł jest wspólnym dziełem Martina Dyera , Alana Frieze i Ravindrana Kannana .

Głównym wynikiem artykułu jest losowy algorytm znajdowania $przybliżenia$$przez$$-wymiarowej$ w przestrzeni euklidesowej założenie istnienia wyrocznia członkowska. Algorytm $wymaga$$_$$,$ wymiarze i _

Algorytm jest wyrafinowanym wykorzystaniem tak zwanej metody łańcuchów Markowa Monte Carlo (MCMC). Podstawowym schematem algorytmu jest prawie jednolite próbkowanie z wnętrza $wykonanie$ umieszczenie siatki składającej się z n -wymiarowych kostek i losowego spaceru po tych kostkach. Wykorzystując teorię szybkiego mieszania się łańcuchów Markowa , wykazali, że potrzeba czasu wielomianu, aby błądzenie losowe osiągnęło rozkład prawie jednorodny.

Wersja algorytmiczna dla podziału regularności Szemerédiego

Ten artykuł jest wspólną pracą Alana Frieze'a i Ravindrana Kannana . $,$ aby wyprowadzić algorytmiczną wersję lematu o regularności Szemerédiego , aby znaleźć -regularny podział.

$_$ : Ustal $wierzchołkami$ niech _ $_$ _ Niech będzie sprawiedliwym podziałem $V}$$\ displaystyle$ w klasach ${\ Displaystyle V_ {0}, V_ {1}, \ ldots, V_ {k}$ . Załóżmy ${\ Displaystyle | V_ {1}|> 4 ^ {2k}}$ i ${\ Displaystyle 4 ^ {k}> 600 \ gamma ^ {2}}$ . Biorąc pod uwagę dowody, że więcej niż par $Displaystyle (V_ {r}, V_ {s})}$$\$ nie jest $}$$\ Displaystyle \ gamma k ^$$($${$ można znaleźć sprawiedliwy podział który jest udoskonaleniem ) na $P}$ klas, z co najwyżej wyjątkową klasą liczności ${\ Displaystyle | V_ {0} | + n/4 ^ {k}}$ i takie, że ${\ Displaystyle \ nazwa operatora {ind} (P ') \ geq \ nazwa operatora {ind} (P) + \ gamma ^ {5}/$

Lemat 2: Niech będzie macierzą z $Displaystyle$$R \ razy C}$${\ Displaystyle | R | = p}$ , ${\ Displaystyle | C | = q}$ i ${\ Displaystyle \| W \ | _ {\ inf} \ równoważnik 1}$$i$ być liczbą rzeczywistą dodatnią (a) Jeśli istnieje ${\ Displaystyle S \ subseteq R}$ , $do {\ Displaystyle T \ subseteq C}$ takie, ${\ Displaystyle | S | \ geq \ gamma p}$ , ${\ Displaystyle | T | \ geq \ gamma q}$ i
${\ Displaystyle | W (S, T) | \ geq \ gamma | S || T |}$ wtedy ${\ Displaystyle \ sigma _ {1} (W) \ geq \ gamma ^ {3} {\ sqrt {pq}}}$ (b) Jeśli ${\ Displaystyle \ sigma _ {1} (W) \ geq \ gamma {\ sqrt {pq}}}$ , to istnieje takie, że ${\ Displaystyle S \ subseteq R}$ , ${\ Displaystyle T \ subseteq C}$${\ Displaystyle | S | \ geq \ gamma 'p$${\ Displaystyle | T | \ geq \ gamma 'q}$ | i $S || T |}$ gdzie ${\ Displaystyle \ gamma '= \ gamma ^ {3}/108}$ . Ponadto $.$ skonstruować w $wielomianowym$

Te dwa lematy są połączone w następującą algorytmiczną konstrukcję lematu o regularności Szemerédiego .

$Arbitralnie$ 1] podziel wierzchołki na sprawiedliwy podział z klasami $V_ {0}, V_$$,$ gdzie ${\ Displaystyle | V_ {i} | \ lfloor n / b \ rfloor}$ i stąd
${\ Displaystyle | V_ {0} | <b}$ . oznaczać ${\ displaystyle k_ {1} = b}$ . [Krok 2] $\ Displaystyle (V_ {r},$ każdej pary oblicz ${\ Displaystyle \ sigma _ {1} (W_ {r, s})}$$( V r , V s )$ dla każdej . Jeśli para
${\ Displaystyle (V_ {r}, V_ {s})}$$\ Displaystyle \gamma =\epsilon ^{9}/108-}$$są$ regularne przez Lemat 2 otrzymujemy dowód, że nie są regularne. [Krok 3] Jeśli jest co najwyżej ${\ Displaystyle \ epsilon \ lewo ({\ rozpocząć {tablica} {c} k_ {1} \\ 2 \\\ koniec {tablica}} \ prawej) }$ pary dające dowody nie
${\ displaystyle \ gamma -}$ regularność, która się zatrzymuje. $}}$$i$ jest . $[$ Krok 4 gdzie $_$ _ $_ \epsilon ^{9}/108}$ i uzyskaj
${\ Displaystyle P '}$ z klasami ${\ Displaystyle 1 + k_ {i} 4 ^ {k_ {i}}}$ [Krok 5] Niech ${\ displaystyle k_ {i} +1 = k_ {i} 4 ^ {k_ {i}}}$ , ${\ Displaystyle P_ {i} +1 = P'}$ , ${\ styl wyświetlania i=i+1}$ i przejdź do kroku 2.

Nagrody i wyróżnienia

• W 1991 roku Frieze otrzymał (wspólnie z Martinem Dyerem i Ravim Kannanem ) Nagrodę Fulkersona w dziedzinie matematyki dyskretnej przyznawaną przez Amerykańskie Towarzystwo Matematyczne i Towarzystwo Programowania Matematycznego . Nagrodę przyznano za artykuł „ Algorytm losowego czasu wielomianowego do aproksymacji objętości ciał wypukłych ” w czasopiśmie Journal of the ACM).
• W 1997 był stypendystą Guggenheima.
• W 2000 roku otrzymał Nagrodę Partnerstwa Wydziału IBM.
• W 2006 roku otrzymał wspólnie (wraz z Michaelem Krivelevichem ) nagrodę Professor Pazy Memorial Research Award od United States-Israel Binational Science Foundation.
• W 2011 roku został wybrany na członka SIAM.
• W 2012 roku został wybrany na członka AMS.
• W 2014 roku wygłosił referat plenarny na Międzynarodowym Kongresie Matematyków w Seulu w Korei Południowej.
• W 2015 roku został wybrany jako Simons Fellow.

Życie osobiste

Frieze jest żonaty z Carol Frieze , która kieruje dwoma działaniami informacyjnymi na wydziale informatyki na Uniwersytecie Carnegie Mellon.

Linki zewnętrzne

• Strona internetowa Alana Frieze'a
• Artykuł nagrodzony nagrodą Fulkersona
• Publikacje Alana Frieze'a w DBLP
• Niektóre prace zarchiwizowane samodzielnie są dostępne tutaj