ミクロス・アタイ

MiklósAjtai （1946年7月2日生まれ）は、米国IBM Almaden Research Centerのコンピューター科学者です。 2003年、彼は、J。KomlósおよびEndreSzemerédiと共同開発した古典的な並べ替えネットワークアルゴリズム、指数下限、分岐プログラムの超線形時空間トレードオフなど、フィールドへの数々の貢献でKnuth賞を受賞しました。ユニークで壮大な」結果。

選択した結果

Ajtaiの結果の一つは、n個のアイテムの鳩の巣原理の命題論理における証明の長さがnの任意の多項式よりも速く成長すると述べています。また、「二次等価な2つの可算構造体も同型である」という文が、ZFCと一貫性があり、独立していることを証明しました。 AjtaiとSzemerédiはコーナー定理を証明しました。これは、Szemerédi定理の高次元一般化への重要なステップです。 KomlósとSzemerédiで、彼はラムジー数R （3、 t ）のct 2 / log tの上限を証明しました。 1995年にのみ、対応する下限が証明され、その結果、彼はフルカーソン賞を獲得しました。 Chvátal、Newborn、およびSzemerédiにより、Ajtaiは交差数の不等式を証明しました。n頂点とmエッジ（ m > 4 n ）のグラフの描画には、少なくともm 3/100 n 2の交差があります。 AjtaiとDworkは、1997年に格子ベースの公開鍵暗号システムを考案しました。 Ajtaiは、格子の問題に関して広範な研究を行ってきました。理論的コンピューターサイエンスにおける数々の貢献により、彼はクヌース賞を受賞しました。

バイオデータ

アジタイは、1976年にハンガリー科学アカデミーから科学の学位を取得しました。 1995年以来、彼はハンガリー科学アカデミーの外部メンバーです。

2012年、彼はアメリカ科学振興協会のフェローに選出されました。

選択された論文

1. Ajtai、M.（1979）、「同型と高次の同値」、 数理論理学、 16 （3）：181–203、doi：10.1016 / 0003-4843（79）90001-9。
2. Ajtai、M .;コムロス、J .; Szemerédi、E.（1982）、「 kキューブの最大ランダム成分」、 Combinatorica 、 2 （1）：1–7、doi：10.1007 / BF02579276。