Алан М. Фриз

Алан М. Фриз (родился 25 октября 1945 года в Лондоне , Англия) — профессор кафедры математических наук Университета Карнеги-Меллона , Питтсбург , США. Он окончил Оксфордский университет в 1966 году и получил докторскую степень в Лондонском университете в 1975 году. Его исследовательские интересы лежат в области комбинаторики , дискретной оптимизации и теоретической информатики . В настоящее время он занимается вероятностными аспектами этих областей; в частности, исследование асимптотических свойств случайных графов , анализ алгоритмов в среднем случае и рандомизированных алгоритмов . Его недавняя работа включала приблизительный подсчет и вычисление объема посредством случайных блужданий ; поиск путей, не пересекающихся по ребрам, в графах-расширителях , а также изучение теории анти-Рамсея и стабильности алгоритмов маршрутизации .

Ключевые вклады

Два ключевых вклада Алана Фриза:

(1) полиномиальный по времени алгоритм аппроксимации объема выпуклых тел

(2) алгоритмическая версия леммы о регулярности Семереди

Оба эти алгоритма будут кратко описаны здесь.

Полиномиальный алгоритм аппроксимации объема выпуклых тел

Бумага — совместная работа Мартина Дайера , Алана Фриза и Равиндрана Каннана .

Основным результатом работы является рандомизированный алгоритм поиска $\epsilon$ приближение к объему выпуклого тела $K$ в $n$-мерного евклидова пространства, предположив существование членства оракула. Алгоритм требует времени, ограниченного полиномом от $n$, размерность $K$ и $1/\epsilon$.

Алгоритм представляет собой сложное использование так называемого метода Монте-Карло цепи Маркова (MCMC).Основная схема алгоритма — практически равномерная выборка изнутри. $K$ поместив сетку, состоящую из n -мерных кубов, и совершив случайное блуждание по этим кубам. Используя теорию быстро перемешивая цепи Маркова , они показывают, что для того, чтобы случайное блуждание приобрело почти равномерное распределение, требуется полиномиальное время.

Алгоритмическая версия разбиения регулярности Семереди

Этот документ представляет собой совместную работу Алана Фриза и Равиндрана Каннана . Они используют две леммы, чтобы вывести алгоритмическую версию леммы о регулярности Семереди, чтобы найти $\epsilon$-обычный раздел.

Лемма 1:
Исправьте k и $\gamma$ и пусть $G=(V,E)$ быть графиком с $n$ вершины. Позволять $P$ быть справедливым разделом $V$ в классах $V_{0},V_{1},\ldots ,V_{k}$. Предполагать $|V_{1}|>4^{2k}$ и $4^{k}>600\gamma ^{2}$. Учитывая доказательства того, что более $\gamma k^{2}$ пары $(V_{r},V_{s})$ не являются $\gamma$-регулярный, то за время O(n) можно найти равное разбиение $P'$ (что является уточнением $P$) в $1+k4^{k}$ классы с исключительным классом мощности не более $|V_{0}|+n/4^{k}$ и такое, что $\operatorname {ind} (P')\geq \operatorname {ind} (P)+\gamma ^{5}/20$

Лемма 2:
Позволять $W$ быть $R\times C$ матрица с $|R|=p$, $|C|=q$ и $\|W\|_{\inf }\leq 1$ и $\gamma$ быть позитивным реальным.
а) Если существуют $S\subseteq R$, $T\subseteq C$ такой, что $|S|\geq \gamma p$, $|T|\geq \gamma q$ и $|W(S,T)|\geq \gamma |S||T|$ затем $\sigma _{1}(W)\geq \gamma ^{3}{\sqrt {pq}}$
(б) Если $\sigma _{1}(W)\geq \gamma {\sqrt {pq}}$, то существуют $S\subseteq R$, $T\subseteq C$ такой, что $|S|\geq \gamma 'p$, $|T|\geq \gamma 'q$ и $W(S,T)\geq \gamma '|S||T|$ где $\gamma '=\gamma ^{3}/108$. Более того, $S$, $T$ можно построить за полиномиальное время.

Эти две леммы объединены в следующую алгоритмическую конструкцию леммы о регулярности Семереди .

[Шаг 1] Произвольно разделите вершины $G$ на справедливый раздел $P_{1}$ с занятиями $V_{0},V_{1},\ldots ,V_{b}$ где $|V_{i}|\lfloor n/b\rfloor$ и, следовательно, $|V_{0}|<b$. обозначать $k_{1}=b$.
[Шаг 2] Для каждой пары $(V_{r},V_{s})$ из $P_{i}$, вычислить $\sigma _{1}(W_{r,s})$. Если пара $(V_{r},V_{s})$ не являются $\epsilon -$регулярны, то по лемме 2 получаем доказательство того, что они не являются $\gamma =\epsilon ^{9}/108-$обычный.
[Шаг 3] Если имеется не более $\epsilon \left({\begin{array}{c}k_{1}\\2\\\end{array}}\right)$ пары, которые дают доказательства отсутствия $\gamma -$регулярность, которая останавливается. $P_{i}$ является $\epsilon -$обычный.
[Шаг 4] Примените лемму 1, где $P=P_{i}$, $k=k_{i}$, $\gamma =\epsilon ^{9}/108$ и получить $P'$ с $1+k_{i}4^{k_{i}}$ занятия
[Шаг 5] Пусть $k_{i}+1=k_{i}4^{k_{i}}$, $P_{i}+1=P'$, $i=i+1$ и перейдите к шагу 2.

Награды и почести

• В 1991 году Фриз получил (совместно с Мартином Дайером и Рави Каннаном ) премию Фулкерсона по дискретной математике, присуждаемую Американским математическим обществом и Обществом математического программирования . Награда была вручена за статью « Алгоритм случайного полиномиального времени для аппроксимации объема выпуклых тел » в журнале ACM).
• В 1997 году он был стипендиатом Гуггенхайма.
• В 2000 году он получил премию IBM Faculty Partnership Award.
• В 2006 году он совместно получил (с Михаилом Кривелевичем ) Премию Мемориала профессора Пазы за исследования от Американо-израильского двунационального научного фонда.
• В 2011 году он был выбран стипендиатом SIAM.
• В 2012 году он был выбран научным сотрудником AMS.
• В 2014 году он выступил с пленарным докладом на Международном конгрессе математиков в Сеуле, Южная Корея.
• В 2015 году он был выбран стипендиатом Simons.
• В 2017 году ему присвоено звание профессора университета.
• В 2022 году он стал профессором Ориона Хоха с 1952 года.

Личная жизнь

Фриз женат на Кэрол Фриз , которая руководит двумя информационно-пропагандистскими мероприятиями на факультете информатики Университета Карнеги-Меллон.

Внешние ссылки

• Веб-страница Алана Фриза
• Статья, получившая премию Фулкерсона
• Публикации Алана Фриза в DBLP
• Некоторые самоархивированные работы доступны здесь.