リチャード・リプトン

リチャード・ジェイ・リプトン（1946年9月6日生まれ）は、ジョージア工科大学計算機学部の研究副学部長、教授、およびフレデリック・G・ストーリー計算機学部長を務めるアメリカの 計算機科学者です。彼は計算機科学理論、暗号学、DNAコンピューティングの研究に携わってきました。

1968年、リプトンはケース・ウェスタン・リザーブ大学で数学の学士号を取得。1973年、カーネギーメロン大学で博士号を取得。デイビッド・パルナスの指導の下、 「On Synchronization Primitive Systems」と題した博士論文を執筆。卒業後、リプトンは1973年から1978年までイェール大学、1978年から1980年までバークレー大学、1980年から2000年までプリンストン大学で教鞭を執った。2000年以降、リプトンはジョージア工科大学に勤務。プリンストン大学在学中、リプトンはDNAコンピューティングの分野で研究を行った。1996年以降、リプトンはテルコルディアの主任コンサルタント科学者を務めている。1999年、リプトンはコンピュータサイエンスの理論の実践への応用により、 全米技術アカデミーの会員に選出された。

1980 年、リプトンはリチャード・M・カープとともに、 SAT が多項式個の論理ゲートを持つブール回路で解ける場合、多項式階層は第 2 レベルまで縮退すること を証明しました。

プログラム P が何らかの特性を持つことを示すことは、プログラム内のアクションが中断不可能な場合は簡単なプロセスです。しかし、アクションが中断可能な場合、リプトンは、ある種の縮約と分析を通じて、元のプログラムがその特性を持つ場合にのみ、縮約されたプログラムがその特性を持つことを示すことができることを示しました。^{[2]中断可能な操作を 1 つの大きな中断不可能なアクションとして扱うことで縮約が行われた場合、これらの緩和された条件でもプログラム P の特性を証明できます。したがって、}並列システムの正当性の証明は、多くの場合大幅に簡素化できます。

リプトンは、データベースのユーザーによるクエリをいつどのように制限すれば、個人情報や秘密情報が漏洩しないかに関するデータベース セキュリティモデルを研究し、作成しました。 ^[3]たとえば、選挙資金のデータベースをクエリすると、ユーザーは選挙候補者や政治団体への個々の寄付を発見できます。データの平均値へのアクセスと無制限のクエリ アクセスが与えられれば、ユーザーは平均値の特性を利用して不正な情報を得ることができます。これらのクエリは、大きな「重複」があり、セキュリティを損ねると考えられています。「重複」とクエリの数を制限することで、安全なデータベースを実現できます。

リチャード・リプトンとアンドリュー・トムキンスはランダム化されたオンライン間隔スケジューリングアルゴリズムを導入した。2サイズバージョンは強力な競争力を持ち、kサイズバージョンはO(log )を達成し、理論的な下限値O(log )を実証した。^[4]このアルゴリズムはランダム化のためにプライベートコインを使用し、中程度の敵を欺くために「仮想」選択を使用する。 ${\displaystyle \vartriangle ^{1+\epsilon }}$${\displaystyle \vartriangle }$

イベントが提示されると、ユーザーはそのイベントをスケジュールに含めるかどうかを決定する必要があります。2 サイズの仮想アルゴリズムは、敵対者が提示する 1 間隔またはk間隔にどのように反応するかによって説明されます。

• 1間隔の場合、公平なコインを投げる

  • ヘッド

    間隔を取る

    テイルス

    「仮想的に」間隔を取りますが、作業は行いません。次の 1 単位の時間には短い間隔を取りません。

• k間隔の場合は、可能な限り実行します。

再び、この 2 サイズ アルゴリズムは強力に競合することが示されています。2サイズ アルゴリズムに類似した一般化されたkサイズ アルゴリズムは、O(log ) 競合することが示されています。 ${\displaystyle \vartriangle ^{1+\epsilon }}$

リプトンは、問題が特定の特性を満たしていれば、ランダム化テストが有用であることが証明された。^[5]プログラムの正しさを証明することは、コンピュータサイエンスで提示される最も重要な問題の 1 つです。通常、ランダム化テストでは、エラーの確率を 1/1000 にするには、1000 回のテストを実行する必要があります。しかし、リプトンは、問題に「簡単な」サブパートがある場合、ブラックボックス テストを繰り返すことでc ^rエラー率を達成できることを示しました。cは 1 未満の定数で、rはテストの数です。したがって、r が増加すると、エラーの確率は指数関数的に急速にゼロになります。

この手法は、多くの種類の問題の正確性を確認するのに役立ちます。

• 信号処理:高速フーリエ変換 (FFT)やその他の高度に並列化可能な関数は、 FORTRANなどのコードで記述すると結果を手動で確認することが難しいため、正確性を迅速に確認する方法が強く求められています。
• 有限体上の関数とパーマネント: がサイズqの有限体上の多項式で、q > deg( ƒ ) + 1であるとします。すると、ƒ は、加算のみを含む関数基底上でdeg( ƒ ) + 1の順序でランダムにテスト可能になります。おそらく、このことから得られる最も重要な応用は、パーマネントの正しさを効率的にチェックできることです。見た目は行列式に似ていますが、パーマネントは正しさをチェックするのが非常に困難です。しかし、この種の問題でも制約を満たしています。この結果は、結果IP = PSPACEを含む、Karloff-Nisan と Shamir の対話型証明システムのブレークスルーにもつながりました。${\displaystyle f(x_{1},\dots,x_{n})}$

ゲーム理論、より具体的には非協力ゲームの分野では、リプトンがE. マルカキス、A. メータとともに、純粋戦略の数の対数的サポートを持つイプシロン均衡戦略の存在を証明しました^[6]。さらに、このような戦略のペイオフは、正確なナッシュ均衡のペイオフをイプシロン近似することができます。サポートの限られた（対数的な）サイズは、イプシロン均衡を計算するための自然な準多項式アルゴリズムを提供します。

LiptonとJ. Naughtonは、データベースクエリのための適応型ランダムサンプリングアルゴリズム^{[7] [8]}を発表しました。これは、クエリの回答が互いに素なサブセットに分割できるクエリに適用できます^{[説明が必要]}。必要なサンプル数を静的に決定するほとんどのサンプリング推定アルゴリズムとは異なり、彼らのアルゴリズムはサンプルのサイズに基づいてサンプル数を決定し、実行時間を一定に保つ傾向があります（サンプル数に比例するのではなく）。

デミロ、リプトン、パーリス^[9]はプログラムの形式検証の考え方を批判し、

• コンピュータサイエンスにおける形式的な検証は、数学における証明と同じような重要な役割を果たすことはありません。
• 継続性の欠如、変更の必然性、および実際のプログラムの仕様の複雑さにより、プログラムの形式検証の正当化と管理が困難になります。

Chandra、Furst、Lipton ^{[10] は、} 2 者間通信プロトコルの概念を、複数者間通信プロトコルに一般化しました。彼らは、プロセスの集合 ( ) が整数の集合 ( 、) にアクセスできるが、そのうちの 1 つだけがにアクセスできないというモデルを提案しました。これらのプロセスは、述語についての合意に達するために通信できます。彼らは、このモデルの通信複雑度 (すべてのプロセス間でブロードキャストされるビット数として定義) を研究しました。例として、彼らは、正確にN (すべての を合計すると N になるか?) に対するk者間プロトコルの複雑度を研究し、タイリング法を使用して下限を取得しました。彼らはさらに、このモデルを一般的な分岐プログラムの研究に適用し、正確にNを計算する定数空間分岐プログラムの時間下限を取得しました。 ${\displaystyle P_{0},P_{1},\ldots ,P_{k-1}}$${\displaystyle a_{0}}$${\displaystyle a_{1},\ldots ,a_{k-1}}$${\displaystyle P_{i}}$${\displaystyle a_{i}}$${\displaystyle a_{i}}$

NP完全であるブール充足可能性問題（しばしばSATと略される）を解くのに、指数的（または少なくとも超多項式的）な時間（これは有名なP対NP問題である）または線形（または少なくとも超対数的）な空間が必要であることを証明する方法はない。しかし、空間と時間のトレードオフの文脈では、時間と空間の両方に制約を適用するとSATを計算できないことを証明することはできる。L . Fortnow、Lipton、D. van Melkebeek、およびA. Viglas ^[11]は、最大でO( n ^1.1 )ステップと最大でO( n ^{0.1 )セルの読み書きテープを使用する}チューリングマシンではSATを計算できないことを証明した。

• グッゲンハイムフェロー、1981年
• 1997年計算機協会フェロー
• 米国工学アカデミー会員^[12]
• 2014年クヌース賞受賞者^[13]

• SL（複雑さ）
• 許可取得保護モデル
• 平面分離定理

• 「結婚式：キャサリン・ファーリー、リチャード・リプトン」、ニューヨーク・タイムズ、2016年6月5日。

• 個人ブログ「ゲーデルの失われた文字と P=NP」