Alan M. Frieze

Alan M. Frieze (född 25 oktober 1945 i London , England) är professor vid institutionen för matematiska vetenskaper vid Carnegie Mellon University, Pittsburgh , USA. Han tog examen från University of Oxford 1966 och doktorerade från University of London 1975. Hans forskningsintressen ligger i kombinatorik , diskret optimering och teoretisk datavetenskap . För närvarande fokuserar han på de probabilistiska aspekterna av dessa områden; i synnerhet studien av de asymptotiska egenskaperna hos slumpmässiga grafer , den genomsnittliga fallanalysen av algoritmer och randomiserade algoritmer . Hans senaste arbete har inkluderat ungefärlig räkning och volymberäkning via slumpmässiga promenader ; hitta osammanhängande kanter i expandergrafer och utforska anti-Ramsey-teorin och stabiliteten hos routingalgoritmer .

Viktiga bidrag

Två viktiga bidrag från Alan Frieze är:

(1) polynomtidsalgoritm för att approximera volymen av konvexa kroppar

(2) Algoritmisk version för Szemerédi regularity lemma

Båda dessa algoritmer kommer att beskrivas kort här.

Polynomtidsalgoritm för att approximera volymen av konvexa kroppar

Tidningen är ett gemensamt verk av Martin Dyer , Alan Frieze och Ravindran Kannan .

Huvudresultatet av uppsatsen är en randomiserad algoritm för att hitta en $\epsilon$ approximation till volymen av en konvex kropp $K$ i $n$ -dimensionell euklidisk rymd genom att anta förekomsten av ett medlemsorakel. Algoritmen tar tid som begränsas av ett polynom i $n$ , dimensionen av $K$ och $1/\epsilon$ .

Algoritmen är en sofistikerad användning av den så kallade Markov-kedjan Monte Carlo- metoden (MCMC). Det grundläggande schemat för algoritmen är en nästan enhetlig sampling inifrån $K$ genom att placera ett rutnät bestående av n -dimensionella kuber och göra en slumpmässig vandring över dessa kuber. Genom att använda teorin om att snabbt blanda Markov-kedjor visar de att det tar en polynomtid för den slumpmässiga vandringen att slå sig ner till en nästan enhetlig fördelning.

Algoritmisk version för Szemerédi regularity partition

Denna artikel är ett kombinerat verk av Alan Frieze och Ravindran Kannan . De använder två lemman för att härleda den algoritmiska versionen av Szemerédi regularitetslemma för att hitta en $\epsilon$ -regular partition.

Lemma 1: Fixa k och $\gamma$ och låt $G=(V,E)$ vara en graf med $n$ hörn. Låt $P$ vara en rättvis partition av $V$ i klasserna $V_{0},V_{1},\ldots ,V_{k}$ . Anta $|V_{1}|>4^{2k}$ och $4^{k}>600\gamma ^{2}$ . Givet bevis på att fler än $\gamma k^{2}$ par $(V_{r},V_{s})$ inte är $\gamma$ -regular, är det möjligt att i O(n) tid hitta en rättvis partition $P'$ (som är en förfining av $P$ ) till $1+ k4^{k}$ klasser, med en exceptionell kardinalitetsklass som mest $|V_{0}|+n/4^{k}$ och så att $\operatorname {ind } (P')\geq \operatörsnamn {ind} (P)+\gamma ^{5}/20$

Lemma 2: Låt $W$ vara en $R\times C$ -matris med $|R|=p$ , $|C|=q$ och $\|W\|_{\inf }\leq 1$ och $\gamma$ är en positiv reell. (a) Om det finns $S\subseteq R$ , $T\subseteq C$ så att $|S|\geq \gamma p$ , $|T|\geq \gamma q$ och $|W(S,T)|\geq \gamma |S||T|$ sedan $\sigma _{1}(W)\geq \gamma ^ {3}{\sqrt {pq}}$ (b) Om ${\displaystyle \sigma _{1}(W)\geq \gamma {\sqrt {pq}}},$ då det finns $S\subseteq R$ , $T\subseteq C$ så att $|S|\geq \gamma 'p$ , $|T|\geq \gamma 'q$ och $W(S,T)\geq \gamma '|S||T|$ där $\gamma '=\gamma ^{3}/108$ . Dessutom $S$ , $T$ konstrueras i polynomtid.

Dessa två lemman kombineras i följande algoritmiska konstruktion av Szemerédi-regelbundenhetslemma .

[Steg 1] Dela godtyckligt hörn av $G$ i en rättvis partition $P_{1}$ med klasserna $V_{0},V_{ 1},\ldots ,V_{b}$ där $|V_{i}|\lgolv n/b\rgolv$ och därmed $|V_{0}|<b$ . beteckna $k_{1}=b$ . [Steg 2] För varje par $(V_{r},V_{s})$ av $P_{i}$ , beräkna $\sigma _{1}(W_{r,s})$ . Om paret $(V_{r},V_{s})$ inte är $\epsilon -$ regelbundet så får vi genom Lemma 2 ett bevis på att de inte är $\gamma =\epsilon ^{9}/108-$ regelbunden. [Steg 3] Om det finns högst $\epsilon \left({\begin{array}{c}k_{1}\\2\\\end{array}}\right)$ par som ger bevis på icke $\gamma -$ regelbundenhet som stannar. $P_{i}$ är $\epsilon -$ regelbunden. [Steg 4] Tillämpa Lemma 1 där $P=P_{i}$ , $k=k_{i}$ , $\gamma = \epsilon ^{9}/108$ och erhåll $P'$ med $1+k_{i}4^{k_{i}}$ klasser [Steg 5] Låt ${\displaystyle k_{i}+1=k_{i}4^{k_{i}}} ,$ P $\displaystyle P_{i}+ 1=P'}$ , $i=i+1$ och gå till steg 2.

Utmärkelser och utmärkelser

• 1991 fick Frieze (tillsammans med Martin Dyer och Ravi Kannan ) Fulkerson-priset i diskret matematik som tilldelas av American Mathematical Society och Mathematical Programming Society . Priset var för uppsatsen " A random polynomial time algorithm for approximating the volym of convex bodies" i Journal of the ACM).
• 1997 var han Guggenheim-stipendiat.
• År 2000 mottog han IBM Faculty Partnership Award.
• 2006 mottog han tillsammans (med Michael Krivelevich ) Professor Pazy Memorial Research Award från United States-Israel Binational Science Foundation.
• 2011 valdes han till SIAM Fellow.
• 2012 valdes han ut som AMS Fellow.
• 2014 höll han ett plenartal vid International Congress of Mathematicians i Seoul, Sydkorea.
• 2015 valdes han ut som Simons Fellow.

Privatliv

Frieze är gift med Carol Frieze , som leder två uppsökande insatser för datavetenskapsavdelningen vid Carnegie Mellon University.

externa länkar

• Alan Friezes webbsida
• Fulkerson prisbelönt papper
• Alan Friezes publikationer på DBLP
• Vissa självarkiverade verk finns tillgängliga här