Loading article…
リチャード・ジェイ・リプトン（1946年9月6日生まれ）は、アメリカのコンピュータ科学者であり、ジョージア工科大学計算機科学部の研究担当副学部長、教授、およびフレデリック・G・ストーレイ記念計算機科学講座教授を務めている。彼は、コンピュータ科学理論、暗号理論、DNAコンピューティングの分野で研究を行ってきた。
1968年、リプトンはケース・ウェスタン・リザーブ大学で数学の学士号を取得しました。1973年にはカーネギーメロン大学で博士号を取得しました。博士論文はデイビッド・パルナスの指導のもと、 「同期プリミティブシステムについて」と題されています。卒業後、リプトンは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 ]このアルゴリズムは、ランダム化のためにプライベートコインを使用し、中程度の敵対者を欺くために「仮想」選択を使用します。
ユーザーはイベントを提示された際に、そのイベントをスケジュールに含めるかどうかを決定する必要があります。2サイズ仮想アルゴリズムは、攻撃者によって提示された1間隔またはk間隔に対してどのように反応するかによって説明されます。
繰り返しになりますが、この 2 サイズ アルゴリズムは非常に競争力があることが示されています。2サイズ アルゴリズムに類似した一般化されたkサイズ アルゴリズムは、O(log）-競争力。
リプトンは、問題が特定の特性を満たしていれば、ランダム化テストが証明可能なほど有用であることを示した。[ 5 ]プログラムの正しさを証明することは、コンピュータサイエンスで提示される最も重要な問題の 1 つです。通常、ランダム化テストでは、エラーの確率を 1/1000 にするには、1000 回のテストを実行する必要があります。しかし、リプトンは、問題に「簡単な」部分がある場合、繰り返しブラックボックステストを行うことでc rエラー率を達成できることを示しました。ここで、c は1 未満の定数で、rはテストの数です。したがって、 r が増加するにつれて、エラーの確率は指数関数的に速くゼロに近づきます。
この手法は、様々な種類の問題の正しさを確認するのに役立ちます。
ゲーム理論、特に非協力ゲームの分野では、リプトンとE.マルカキス、A.メータが[ 6 ]純粋戦略の数に対して対数的なサポートを持つε均衡戦略の存在を証明した。さらに、そのような戦略の利得は、厳密なナッシュ均衡の利得をε近似することができる。サポートの限られた（対数的な）サイズは、ε均衡を計算するための自然な準多項式アルゴリズムを提供する。
LiptonとJ. Naughtonは、データベースクエリのための適応型ランダムサンプリングアルゴリズム[ 7 ] [ 8 ]を発表しました。このアルゴリズムは、クエリに対する回答を互いに素な部分集合に分割できるあらゆるクエリに適用できます。ほとんどのサンプリング推定アルゴリズムは必要なサンプル数を静的に決定しますが、彼らのアルゴリズムはサンプルのサイズに基づいてサンプル数を決定し、実行時間を一定に保つ傾向があります（サンプル数に対して線形ではありません）。
デミロ、リプトン、パーリス[ 9 ]はプログラムの形式検証の考え方を批判し、
Chandra、Furst、Lipton [ 10 ]は、2 者間通信プロトコルの概念を多者間通信プロトコルに一般化した。彼らは、プロセス群 (）整数のセットにアクセスできる（、) そのうちの 1 つを除いて、アクセスが拒否されましたこれらのプロセスは、述語に関する合意に達するために通信することが許可されています。彼らは、すべてのプロセス間でブロードキャストされるビット数として定義される、このモデルの通信複雑性を研究しました。例として、彼らは、Exactly -N (do all)のkパーティ プロトコルの複雑性を研究しました。は、合計が N になるか？) を研究し、タイル法を使用して下限を得ました。さらに、このモデルを一般的な分岐プログラムの研究に適用し、正確にNを計算する定数空間分岐プログラムの時間の下限を得ました。
NP完全問題であるブール充足可能性問題（しばしばSATと略される）を解くのに指数時間（または少なくとも多項式時間）（これは有名なP対NP問題である）や線形空間（または少なくとも対数空間）が必要であることを証明する方法はない。しかし、空間と時間のトレードオフの文脈では、時間と空間の両方に制約を適用するとSATを計算できないことを証明できる。L . Fortnow、Lipton、D. van Melkebeek、およびA. Viglas [ 11 ]は、最大O( n 1.1 )ステップ、最大O( n 0.1 )セルの読み書きテープを使用するチューリングマシンではSATを計算できないことを証明した。
