アラン・M・フリーズ

アラン・M・フリーズ（1945年10月25日、イギリス、ロンドン生まれ）は、アメリカ合衆国ピッツバーグのカーネギーメロン大学数理科学科教授。1966年にオックスフォード大学を卒業し、 1975年にロンドン大学で博士号を取得。研究対象は、組合せ論、離散最適化、理論計算機科学。現在は、これらの分野の確率的側面、特にランダムグラフの漸近的特性、アルゴリズムの平均ケース分析、ランダム化アルゴリズムの研究に重点を置いている。最近の研究には、ランダムウォークによる近似カウントとボリューム計算、エキスパンダーグラフでのエッジ素パスの検出、反ラムゼー理論とルーティングアルゴリズムの安定性の調査などがある。

Alan Frieze による 2 つの重要な貢献は次のとおりです。

（１）凸体の体積を近似する多項式時間アルゴリズム

(2) Szemerédi の規則性補題のアルゴリズム バージョン

ここでは、これら両方のアルゴリズムについて簡単に説明します。

論文 ^[1]はMartin Dyer、Alan Frieze、Ravindran Kannan の共同研究である。

この論文の主な結果は、メンバーシップオラクルの存在を仮定して、次元ユークリッド空間内の凸体の体積の近似値を見つけるためのランダム化アルゴリズムです。このアルゴリズムは、 の多項式、 の次元、によって制限される時間がかかります。 ${\displaystyle \epsilon}$${\displaystyle K}$${\displaystyle n}$${\displaystyle n}$${\displaystyle K}$${\displaystyle 1/\epsilon }$

このアルゴリズムは、いわゆるマルコフ連鎖モンテカルロ(MCMC) 法を高度に利用したものです。アルゴリズムの基本的なスキームは、n次元の立方体からなるグリッドを配置し、これらの立方体上でランダム ウォークを実行することによって、内部からほぼ均一なサンプリングを行うことです。急速に混合するマルコフ連鎖の理論を使用することで 、ランダム ウォークがほぼ均一な分布に落ち着くまでに多項式時間がかかることが示されています。 ${\displaystyle K}$

この論文 ^{[2]は、アラン・フリーズと}ラビンドラン・カンナン の共同研究です。彼らは2つの補題を使用して、 Szemerédi正則性補題のアルゴリズムバージョンを導出し、正則分割を見つけます。 ${\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}$

これら 2 つの補題は、次のSzemerédi 正則性補題のアルゴリズム構築で組み合わされます。

[ステップ 1]の頂点を、 および のクラスを持つ公平な分割に任意に分割します。したがって、 と表します。[ ステップ 2]のすべてのペアについて、 を計算します。ペアが正則でない場合、補題 2 により、それらが正則でないことが証明されます。 [ステップ 3]非正則性の証明を生成するペアが最大で ある場合、は停止します。 は正則 です。 [ステップ 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 年、フリーズはマーティン・ダイアーおよびラヴィ・カンナンと共同で、アメリカ数学会および数理計画学会より離散数学におけるフルカーソン賞を受賞した。この賞は、Journal of the ACM に掲載された論文「凸体の体積を近似するランダム多項式時間アルゴリズム」に対して授与された。
• 1997年にグッゲンハイムフェローに選出された。
• 2000 年に IBM Faculty Partnership Award を受賞。
• 2006年、彼はマイケル・クリベレヴィッチと共同で、米国・イスラエル二国間科学財団よりパジー教授記念研究賞を受賞した。
• 2011年にSIAMフェローに選出された。^[3]
• 2012年にAMSフェローに選出された。^[4]
• 2014年に韓国ソウルで開催された国際数学者会議で全体講演を行った。
• 2015年にシモンズフェローに選出された。
• 2017年に大学教授に昇進した。
• 2022年に彼はOrion Hoch, S 1952教授に就任しました。

フリーズは、カーネギーメロン大学のコンピュータサイエンス学部の2つのアウトリーチ活動を指揮しているキャロル・フリーズと結婚している。 ^[5]

• アラン・フリーズのウェブページ
• フルカーソン賞受賞論文
• DBLP における Alan Frieze の出版物
• セルフアーカイブされた作品の一部はここで閲覧可能です