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

Два ключевых достижения Алана Фрайзе:(1) Полиномиальное время для приближенного вычисления объема выпуклых тел(2) Аппаратная версия леммы регулярности СёмередиОба алгоритма будут описаны ниже.=

=

Эта работа является совместным трудом Мартина Дайера, Алана Фрайзе и Равидрана Канны. Основной результат — это случайный метод для нахождения ϵ {\displaystyle \epsilon } -приближенного объема выпуклого тела K в n-мерном евклидовом пространстве, используя предположение о существовании членства (члена) ортогонала. Алгоритм работает за время полинома от n и 1/ϵ.Алгоритм основан на методе Марковских цепей Монте-Карло для случайного выборки точек внутри K, используя сетку из кубов в пространстве и рандомизированные переходы между ними. С помощью теории быстро смешивающихся марковских процессов доказывается быстрое достижение почти равномерной распределенности.=

Эта работа — совместный труд Фрайзе и Канны, в которой они предложили алгебраическую интерпретацию известного результата.Они используют два леммы для получения алгоритмической версии регулярного леммы Сзёмереди, чтобы найти разбиение с параметром ε-регулярности.Лемма 1: Пусть k и γ — фиксированные числа. Рассмотрим граф G = (V,E) c n вершинами. Раздел P делит V на классы Vi0, ..., Vk так, чтобы |Vi1| > 4^(2k), а 4^k ≥ 600 * γ².Если доказано, что больше чем γ*k² пар (Vi, Vj) не являются ε-регулярными, то можно найти в O(n) времени более детализированное разбиение P' с числом классов до k + 1 и исключительным классом размера |V0| ≤ |V0| + n/4^k. При этом индекс регулярности увеличивается минимум на γ⁵ / 20.Лемма 2: Пусть W — матрица R x C с p строками, q столбцами и нормой ||W||inf не более единицы (1). Для положительного числа ε можно найти такое разбиение классов в каждом измерении, что произведения подматриц будут иметь ограниченную регуляризацию.Если существуют такие множества \( S\subseteq R\) и \( T\subseteq C \), что их размеры удовлетворяют условиям:\[ |S|\geq \gamma p, \quad |T|\geq \gamma q \]и объединение этих двух множеств в матрице W (например, пересечение или сумма) имеет минимальный порог \(|W(S,T)|\geq \gamma |S||T|\), то выполняется неравенство:\[ \sigma_1(W)\geq \gamma^3{\sqrt{pq}}. \]Если же для матрицы W выполнено условие\[ \sigma_1(W) \geq \gamma {\sqrt {pq}}, \]то существуют такие \( S\subseteq R\) и \( T\subseteq C \), что их размеры будут не меньше:\[ |S|\geq \frac{\gamma^3}{108} p, \quad |T| \geq \frac{\gamma^3}{108} q. \] Здесь \(\sigma_1(W)\) — это первый собственный вектор матрицы W.\n\nFurthermore, S T can be constructed in polynomial time.\nThese two lemmas are combined in the following algorithmic construction of Szemerédi's regularity lemma.[Step 1] Разделим вершины графа G на равномерные группы P₁ (с классами V₀ до Vₖ), где k = b, и |Vᵢ| ≈ n/b. Если в группе V₀ меньше элементов чем b, то обозначим её размер как k₁.[Step 2] Для каждой пары вершинных множеств (Vi, Vs) из P_i вычисляем параметр σ1(Wrs). В случае если пара не является ε-регулярной согласно Лемме 2, она будет доказана нерегулярностью с γ = ε⁹/108.[Шаг 3] Если существует не более чем ε пар, которые дают доказательства непрерывности и останавливаются. P i {\displaystyle P_{i}} является регулярным с точностью до ϵ [Шаг 4] Применить Лемму 1 для случая, где P i = ε^9 / (108) и получить P' с количеством классов:\[ 1 + k_i \cdot 4^{k_i} \][Шаг 5] Пусть ki+1 = ki * 4^(ki) - это новое значение для k. Обновим значения: Pi+1 = P' и увеличить i на единицу. Перейти к шагу 2.\begin{itemize} \item Награды и почести: В 1991 году (совместно с Мартином Дайером и Рави Каннаном) получил премию Fulkerson Prize, присуждаемую Американским математическим обществом и Обществом программирования. Премия была за статью 'A random polynomial time algorithm for approximating the volume of convex bodies' в журнале Journal of the ACM. \item 1997 год: стипендист Гуггенхайма (Guggenheim Fellow). \item В 2000 году — награда IBM Faculty Partnership Award. \item В 2006-м вместе с Михаилом Кривелевичем получили премию памяти профессора Пази от Фонда научного сотрудничества США и Израиля (US-Israel Binational Science Foundation). ...\end{itemize}