Алан М. Фриз

британский математик

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

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

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

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

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

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

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

Статья ^[1] является совместной работой Мартина Дайера , Алана Фриза и Равиндрана Каннана .

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

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

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

Эта статья ^[2] является совместной работой Алана Фриза и Равиндрана Каннана . Они используют две леммы для вывода алгоритмической версии леммы Семереди о регулярности для нахождения -регулярного разбиения. ${\displaystyle \epsilon }$

Лемма 1:
Зафиксируем k и и пусть будет графом с вершинами. Пусть будет справедливым разбиением на классы . Предположим и . Учитывая доказательства того, что более пар не являются -регулярными, можно найти за время O(n) справедливое разбиение (которое является уточнением ) на классы с исключительным классом мощности не более и таким, что ${\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}$

Лемма 2:
Пусть будет матрицей с , и и будет положительным вещественным числом. (a) Если существуют , такие что , и тогда (b) Если , то существуют , такие что , и где . Более того, , можно построить за полиномиальное время. ${\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}$

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

[Шаг 1] Произвольно разделим вершины на равноправное разбиение с классами , где и, следовательно , . обозначим . [Шаг 2] Для каждой пары вычислим . Если пара не является регулярной, то по лемме 2 мы получаем доказательство того, что они не являются регулярными. [Шаг 3] Если существует не более пар, которые дают доказательства нерегулярности , то halt. является регулярным. [Шаг 4] Применим лемму 1, где , , и получим с классами [Шаг 5] Пусть , , и перейдем к шагу 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}$

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

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

Личная жизнь

Фриз женат на Кэрол Фриз , которая руководит двумя просветительскими проектами для факультета компьютерных наук в Университете Карнеги — Меллона. ^[5]

Ссылки

1. М. Дайер, А. Фриз и Р. Каннан (1991). «Случайный полиномиальный алгоритм аппроксимации объема выпуклых тел». Журнал ACM . Т. 38, № 1. С. 1–17.
2. А. Фриз и Р. Каннан (1999). "Простой алгоритм построения разбиения регулярности Семереди" (PDF) . Electron. J. Comb . Том 6.
3. Выпуск стипендиатов Siam 2011 г.
4. Список членов Американского математического общества, получен 29 декабря 2012 г.
5. Фриз, Кэрол, Персональные данные, Университет Карнеги — Меллона , получено 20 января 2019 г.

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

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