Alan M. Frieze

Matemático británico

Alan M. Frieze (nacido el 25 de octubre de 1945 en Londres , Inglaterra) es profesor en el Departamento de Ciencias Matemáticas de la Universidad Carnegie Mellon , Pittsburgh , Estados Unidos. Se graduó de la Universidad de Oxford en 1966 y obtuvo su doctorado de la Universidad de Londres en 1975. Sus intereses de investigación se centran 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 los grafos aleatorios , el análisis de casos promedio de algoritmos y los algoritmos aleatorizados . Su trabajo reciente ha incluido el conteo aproximado y el cálculo de volumen mediante paseos aleatorios ; la búsqueda de caminos disjuntos de aristas en grafos expansores y la exploración de la teoría anti-Ramsey y la estabilidad de los algoritmos de enrutamiento .

Contribuciones clave

Dos contribuciones claves realizadas 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 hallar una aproximación al volumen de un cuerpo convexo en un espacio euclidiano de dimensión 1, suponiendo la existencia de un oráculo de pertenencia. El algoritmo toma un tiempo limitado 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 de Monte Carlo de cadenas de Markov (MCMC). El esquema básico del algoritmo es un muestreo casi uniforme desde dentro colocando una cuadrícula que consiste en cubos n -dimensionales y haciendo un recorrido aleatorio sobre estos cubos. Al usar la teoría de la mezcla rápida de cadenas de Markov , demuestran que se necesita un tiempo polinomial para que el recorrido aleatorio se estabilice 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:
Fijemos k y y sea un grafo con vértices. Sea una partición equitativa de en clases . Supongamos que 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 existen , tales que , y entonces (b) Si , entonces existen , tales 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 . denote . [Paso 2] Para cada par de , calcule . Si el par no es regular, entonces por el Lema 2 obtenemos una prueba de que no son regulares. [Paso 3] Si hay como máximo pares que producen pruebas de no regularidad de que halt. es regular. [Paso 4] Aplique el Lema 1 donde , , y obtenga con clases [Paso 5] Sea , , 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 American Mathematical Society y la Mathematical Programming Society . El premio fue otorgado por el artículo " Un algoritmo de tiempo polinomial aleatorio para aproximar el volumen de cuerpos convexos " publicado 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 Profesor Pazy Memorial de la Fundación Binacional de Ciencias Estados Unidos-Israel.
• En 2011 fue seleccionado como SIAM Fellow. ^[3]
• En 2012 fue seleccionado como AMS Fellow. ^[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 fue nombrado profesor Orion Hoch, S 1952.

Vida personal

Frieze está casado con Carol Frieze , quien dirige dos iniciativas de extensió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 polinomial 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) . Electron. J. Comb . Vol. 6.
3. Clase de becarios Siam de 2011
4. Lista de miembros de la American Mathematical Society, 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
• Algunas obras autoarchivadas están disponibles aquí