Alan M. Friso

matemático británico

Alan M. Frieze (nacido el 25 de octubre de 1945 en Londres , Inglaterra) es profesor del Departamento de Ciencias Matemáticas de la Universidad Carnegie Mellon , Pittsburgh , Estados Unidos. Se graduó en la Universidad de Oxford en 1966 y obtuvo su doctorado en la Universidad de Londres en 1975. Sus intereses de investigación se encuentran en la combinatoria , la optimización discreta y la informática teórica . Actualmente se centra en los aspectos probabilísticos de estas áreas; en particular, el estudio de las propiedades asintóticas de gráficos aleatorios , el análisis de casos promedio de algoritmos y algoritmos aleatorios . Su trabajo reciente ha incluido recuento aproximado y cálculo de volumen mediante paseos aleatorios ; encontrar caminos disjuntos de bordes en gráficos de expansión y explorar la teoría anti-Ramsey y la estabilidad de los algoritmos de enrutamiento .

Contribuciones clave

Dos contribuciones clave hechas por Alan Frieze son:

(1) algoritmo de tiempo polinomial para aproximar el volumen de cuerpos convexos

(2) versión algorítmica del lema de regularidad de Szemerédi

Ambos algoritmos se describirán brevemente aquí.

Algoritmo de tiempo polinomial para aproximar el volumen de cuerpos convexos.

El artículo ^[1] es un trabajo conjunto de Martin Dyer , Alan Frieze y Ravindran Kannan .

El resultado principal del artículo es un algoritmo aleatorio para encontrar una aproximación al volumen de un cuerpo convexo en un espacio euclidiano de dimensiones suponiendo la existencia de un oráculo de membresía. El algoritmo toma un tiempo acotado por un polinomio en , la dimensión de y . ${\displaystyle \epsilon }$ ${\displaystyle K}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle K}$ ${\displaystyle 1/\epsilon }$

El algoritmo es un uso sofisticado del llamado método Monte Carlo de cadena de Markov (MCMC). El esquema básico del algoritmo es un muestreo casi uniforme desde dentro colocando una cuadrícula que consta de cubos de n dimensiones y realizando un recorrido aleatorio sobre estos cubos. Al utilizar la teoría de la mezcla rápida de cadenas de Markov , muestran que se necesita un tiempo polinómico para que el paseo aleatorio se establezca y se convierta en una distribución casi uniforme. ${\displaystyle K}$

Versión algorítmica para la partición de regularidad Szemerédi

Este artículo ^[2] es un trabajo combinado de Alan Frieze y Ravindran Kannan . Utilizan dos lemas para derivar la versión algorítmica del lema de regularidad de Szemerédi para encontrar una partición regular. ${\displaystyle \epsilon }$

Lema 1:
Arregle k y y sea un gráfico con vértices. Sea una partición equitativa de en clases . Supongamos y . Dadas las pruebas de que más de pares no son regulares, es posible encontrar en tiempo O(n) una partición equitativa (que es un refinamiento de ) en clases, con una clase excepcional de cardinalidad como máximo y tal que ${\displaystyle \gamma }$ ${\displaystyle G=(V,E)}$ ${\displaystyle n}$ ${\displaystyle P}$ ${\displaystyle V}$ ${\displaystyle V_{0},V_{1},\ldots ,V_{k}}$ ${\displaystyle |V_{1}|>4^{2k}}$ ${\displaystyle 4^{k}>600\gamma ^{2}}$ ${\displaystyle \gamma k^{2}}$ ${\displaystyle (V_{r},V_{s})}$ ${\displaystyle \gamma }$ ${\displaystyle P'}$ ${\displaystyle P}$ ${\displaystyle 1+k4^{k}}$ ${\displaystyle |V_{0}|+n/4^{k}}$ ${\displaystyle \operatorname {ind} (P')\geq \operatorname {ind} (P)+\gamma ^{5}/20}$

Lema 2:
Sea una matriz con , y y un real positivo. (a) Si existe , tal que , y entonces (b) Si , entonces existe , tal que , y donde . Además, , se puede construir en tiempo polinomial. ${\displaystyle W}$ ${\displaystyle R\times C}$ ${\displaystyle |R|=p}$ ${\displaystyle |C|=q}$ ${\displaystyle \|W\|_{\inf }\leq 1}$ ${\displaystyle \gamma }$
${\displaystyle S\subseteq R}$ ${\displaystyle T\subseteq C}$ ${\displaystyle |S|\geq \gamma p}$ ${\displaystyle |T|\geq \gamma q}$ ${\displaystyle |W(S,T)|\geq \gamma |S||T|}$ ${\displaystyle \sigma _{1}(W)\geq \gamma ^{3}{\sqrt {pq}}}$
${\displaystyle \sigma _{1}(W)\geq \gamma {\sqrt {pq}}}$ ${\displaystyle S\subseteq R}$ ${\displaystyle T\subseteq C}$ ${\displaystyle |S|\geq \gamma 'p}$ ${\displaystyle |T|\geq \gamma 'q}$ ${\displaystyle W(S,T)\geq \gamma '|S||T|}$ ${\displaystyle \gamma '=\gamma ^{3}/108}$ ${\displaystyle S}$ ${\displaystyle T}$

Estos dos lemas se combinan en la siguiente construcción algorítmica del lema de regularidad de Szemerédi .

[Paso 1] Divida arbitrariamente los vértices de en una partición equitativa con clases donde y por lo tanto . denotar . [Paso 2] Para cada par de , calcule . Si el par no es regular, mediante el Lema 2 obtenemos una prueba de que no son regulares. [Paso 3] Si hay como máximo pares que produzcan pruebas de no regularidad, se detendrán. es regular. [Paso 4] Aplique el Lema 1 donde , y obtenga con clases. [Paso 5] Deje , y vaya al Paso 2. ${\displaystyle G}$ ${\displaystyle P_{1}}$ ${\displaystyle V_{0},V_{1},\ldots ,V_{b}}$ ${\displaystyle |V_{i}|\lfloor n/b\rfloor }$ ${\displaystyle |V_{0}|<b}$ ${\displaystyle k_{1}=b}$
${\displaystyle (V_{r},V_{s})}$ ${\displaystyle P_{i}}$ ${\displaystyle \sigma _{1}(W_{r,s})}$ ${\displaystyle (V_{r},V_{s})}$ ${\displaystyle \epsilon -}$ ${\displaystyle \gamma =\epsilon ^{9}/108-}$
${\displaystyle \epsilon \left({\begin{array}{c}k_{1}\\2\\\end{array}}\right)}$ ${\displaystyle \gamma -}$ ${\displaystyle P_{i}}$ ${\displaystyle \epsilon -}$
${\displaystyle P=P_{i}}$ ${\displaystyle k=k_{i}}$ ${\displaystyle \gamma =\epsilon ^{9}/108}$ ${\displaystyle P'}$ ${\displaystyle 1+k_{i}4^{k_{i}}}$
${\displaystyle k_{i}+1=k_{i}4^{k_{i}}}$ ${\displaystyle P_{i}+1=P'}$ ${\displaystyle i=i+1}$

Premios y honores

• En 1991, Frieze recibió (junto con Martin Dyer y Ravi Kannan ) el Premio Fulkerson en Matemáticas Discretas otorgado por la Sociedad Estadounidense de Matemáticas y la Sociedad de Programación Matemática . El premio fue por el artículo " Un algoritmo de tiempo polinómico aleatorio para aproximar el volumen de cuerpos convexos " en el Journal of the ACM).
• En 1997 fue becario Guggenheim.
• En 2000, recibió el premio IBM Faculty Partnership Award.
• En 2006 recibió conjuntamente (con Michael Krivelevich ) el Premio de Investigación en Memoria del Profesor Pazy de la Fundación Binacional de Ciencias Estados Unidos-Israel.
• En 2011 fue seleccionado como SIAM Fellow. ^[3]
• En 2012 fue seleccionado como miembro de AMS. ^[4]
• En 2014 dio una charla plenaria en el Congreso Internacional de Matemáticos en Seúl, Corea del Sur.
• En 2015 fue seleccionado como Simons Fellow.
• En 2017 fue ascendido a profesor universitario.
• En 2022 se convirtió en profesor Orion Hoch, S 1952.

Vida personal

Frieze está casado con Carol Frieze , quien dirige dos esfuerzos de divulgación para el departamento de informática de la Universidad Carnegie Mellon. ^[5]

Referencias

1. M. Dyer, A. Frieze y R. Kannan (1991). "Un algoritmo aleatorio de tiempo polinómico para aproximar el volumen de cuerpos convexos". Revista de la ACM . vol. 38, núm. 1. págs. 1–17.
2. A. Frieze y R. Kannan (1999). "Un algoritmo simple para construir la partición de regularidad de Szemere'di" (PDF) . Electrón. J. Peine . vol. 6.
3. Promoción de 2011 de Siam Fellows
4. Lista de miembros de la Sociedad Estadounidense de Matemáticas, consultado el 29 de diciembre de 2012.
5. Frieze, Carol, Personal, Carnegie Mellon University , consultado el 20 de enero de 2019

enlaces externos

• Página web de Alan Frieze
• Artículo ganador del premio Fulkerson
• Publicaciones de Alan Frieze en DBLP
• Ciertas obras autoarchivadas están disponibles aquí.