マイケル・サックス（数学者）

マイケル・エズラ・サックスはアメリカの数学者。現在はラトガース大学数学科長（2017年～）であり、2006年から2010年まではラトガース大学数学大学院プログラムのディレクターを務めた。サックスは、指導教官のダニエル・J・クライトマンの指導の下、「有限集合系の双対性特性」[1]と題する論文を完成させ、1980年にマサチューセッツ工科大学で博士号を^取得した。

彼の出版物と共同研究のリストはDBLPで見ることができます。^[2]

2016年に彼は計算機協会のフェローになった。^{[3] [4]}

サックスの計算複雑性理論、組合せ論、グラフ理論の研究は、順序理論の下限値、ランダム化計算、空間と時間のトレードオフの研究に貢献しました。

1984年、サックスとジェフ・カーンは、乗法定数までの部分的に順序付けられた情報の下でのソートには厳密な情報理論的下限が存在することを示しました。 ^[5]

[1]では、ノイズブロードキャスト問題の最初の超線形下限が証明されました。ノイズブロードキャストモデルでは、プロセッサにローカル入力ビットが割り当てられます。各プロセッサは、受信ビットが一定の確率で独立して反転される可能性がある他のすべてのプロセッサへのノイズブロードキャストを実行できます。問題は、プロセッサが何らかの関数 を決定することです。Saksらは、Gallagerによる既存のプロトコルが、一般化されたノイズ決定木からの縮小によって実際に最適であることを示し、入力を学習する木の深さの下限を生み出しました。^[6]${\displaystyle n+1}$${\displaystyle P_{0},P_{1},\ldots ,P_{n}}$${\displaystyle x_{i}}$${\displaystyle P_{0}}$${\displaystyle f(x_{1},x_{2},\ldots,x_{n})}$${\displaystyle f}$${\displaystyle \Omega (n\log(n))}$

2003年、P. Beame、Saks、X. Sun、E. Veeは、決定問題のランダム化計算における時間と空間の下限のトレードオフが証明された最初の論文を発表しました。^[7]

Saks 氏は以下のジャーナル編集委員会で役職を務めています。

• SIAM Journal on Computing副編集長
• Combinatorica編集委員
• グラフ理論ジャーナル編集委員
• 離散応用数学編集委員

• Borodin, Allan; Linial, Nathan; Saks, Michael E. (1992-10-01). 「韻律タスクシステムのための最適なオンラインアルゴリズム」Journal of the ACM . 39 (4): 745–763. doi : 10.1145/146585.146588 . ISSN  0004-5411. S2CID  18783826.
• Fredman, M.; Saks, M. (1989-02-01) 「動的データ構造のセル プローブ複雑性」第 21 回 ACM 計算理論シンポジウム議事録 - STOC '89 。米国ニューヨーク州ニューヨーク: Association for Computing Machinery。pp. 345–354。doi : 10.1145/ 73007.73040。ISBN 978-0-89791-307-2. S2CID  13470414。
• Paturi, Ramamohan; Pudlák, Pavel; Saks, Michael E.; Zane, Francis (2005-05-01). 「k-SAT の改良指数時間アルゴリズム」Journal of the ACM . 52 (3): 337–364. doi :10.1145/1066100.1066101. ISSN  0004-5411.
• Goldberg, Andrew V.; Hartline, Jason D.; Karlin , Anna R.; Saks, Michael; Wright, Andrew (2006-05-01). 「競争オークション」。ゲームと経済行動。ミニ特集号: 電子市場設計。55 (2): 242–269。doi : 10.1016 /j.geb.2006.02.003。ISSN 0899-8256  。
• Saks, Michael; Zaharoglou, Fotios (2000-01-01). 「待機なしの k セット合意は不可能: 公開知識のトポロジー」。SIAM Journal on Computing . 29 (5): 1449–1483. doi :10.1137/S0097539796307698. ISSN  0097-5397.
• Saks, Michael; Wigderson, Avi (1986 年 10 月)。「確率的ブール決定木とゲーム木の評価の複雑さ」。第 27 回コンピュータ サイエンスの基礎に関する年次シンポジウム (SFCS 1986)。pp. 29–38。doi : 10.1109 / SFCS.1986.44。ISBN 0-8186-0740-8. S2CID  6130392。
• Saks, Michael; Yu, Lan (2005-06-05)。「弱い単調性は凸領域での真実性に十分である」。第6 回 ACM 電子商取引会議の議事録。EC '05。ニューヨーク、ニューヨーク州、米国: Association for Computing Machinery。pp. 286–293。doi : 10.1145/1064009.1064040。ISBN 978-1-59593-049-1. S2CID  2135397。

• 数学系譜プロジェクトのマイケル・エズラ・サックス