ナティ・リニアル

ネイサン（ナティ）・リニアル（1953年イスラエルのハイファ生まれ）^[1]は、イスラエルの数学者、コンピュータ科学者であり、エルサレム・ヘブライ大学のレイチェル・アンド・セリム・ベニン・コンピュータサイエンス・エンジニアリング学部の教授であり、^[2] ISIの高引用研究者でもある。^[3]

リニアルはテクニオンで学士課程を修了し、1978年にヘブライ大学でミカ・パールズの指導の下博士号を取得した。^{[1] [4]}彼はヘブライ大学に教員として戻る前は、カリフォルニア大学ロサンゼルス校で大学院研究員を務めていた。 ^[1]

2012年にアメリカ数学会のフェローに就任。^{[5] 2019年にはイシャイ・マンスール、}ノアム・ニサンと共著した論文「Constant Depth Circuits, Fourier Transform, and Learnability 」でFOCS Test of Time Awardを受賞。^[6]

• リニアル、ナティ (1992)、「分散グラフ アルゴリズムにおける局所性」、SIAM J. Comput.、21 (1): 193–201、CiteSeerX  10.1.1.471.6378、doi :10.1137/0221015この論文は 2013 年のダイクストラ賞を受賞しました。賞の審査委員会は次のように語っています。「この論文は分散メッセージ パッシング アルゴリズムに大きな影響を与えました。分散コンピューティングにおける局所性の概念にスポットライトを当て、さまざまな分散問題の局所性レベルについて、さまざまなネットワーク クラスにおける時間計算量の観点から興味深い疑問を提起しました。その目標に向けて、この論文で Linial は、メッセージ サイズ、非同期性、障害を無視する、局所性の研究に特に適したモデルを開発しました。この明確なモデルにより、研究者は局所性の影響を分離し、グラフ理論の概念としての距離と近傍の役割、および分散コンピューティングにおけるアルゴリズムと計算量理論の問題との相互関係を研究することができました。」^[7]
• ボロディン、アラン; リニアル、ネイサン;サックス、マイケル E. (1992)、「韻律タスクシステムのための最適なオンラインアルゴリズム」、J. ACM、39 (4): 745–763、doi : 10.1145/146585.146588、S2CID  18783826オンライン アルゴリズムの競合分析に関するこの論文では、将来のリクエストを知らずに一連のリクエストを処理する方法を決定する必要があるタスクの非常に一般的なモデルであるメトリック タスク システムについて検討します。メトリック タスク システム モデルを紹介し、さまざまなスケジューリング問題をモデル化するためにこのモデルを使用する方法を説明し、多くの状況で最適に機能することが証明されているアルゴリズムを開発します。
• リニアル、ネイサン; マンスール、イシャイ;ニサン、ノアム(1993)、「定数深度回路、フーリエ変換、学習可能性」、J. ACM、40 (3): 607–620、doi : 10.1145/174130.174138、S2CID  16978276複雑性クラスAC ⁰ (高度に並列化可能な計算問題を表すクラス)の関数に対して調和解析を実行することにより、Linial 氏と共著者は、これらの関数が疑似乱数ジェネレーターとして適切に動作しないこと、多項式によって適切に近似できること、機械学習システムによって効率的に学習できることを示しました。
• リニアル、ネイサン; ロンドン、エラン; ラビノビッチ、ユーリ (1995)、「グラフの幾何学とそのアルゴリズム的応用のいくつか」、コンビナトリカ、15 (2): 215–245、doi :10.1007/BF01200757、S2CID  5071936Google Scholarによると、Linial の最も引用されている論文であるこの論文は、マルチコモディティフロー問題などのグラフ理論的問題と、ジョンソン・リンデンシュトラウスの補題によって与えられるような低次元空間への距離空間の低歪み埋め込みとの間の関連性を探っています。
• Hoory, Shlomo; Linial, Nathan; Wigderson, Avi (2006)、「Expander graphs and their applications」、米国数学会誌、43 (4): 439–561、doi : 10.1090/S0273-0979-06-01126-8、MR  22479192008年にリニアルと共著者らは、この論文「エキスパンダーグラフに関する概説」により、アメリカ数学会のリーバイ・L・コナント賞を受賞しました。^[1]