サリル・ヴァダン

サリル・ヴァダン
サリル・ヴァダン
市民権	アメリカ合衆国
教育	ハーバード大学（BA） マサチューセッツ工科大学（PhD）
知られている	ジグザグ製品
受賞歴	ACM博士論文賞、2000年 ゲーデル賞、2009年
科学者としてのキャリア
フィールド	計算複雑性理論、暗号理論
機関	ハーバード大学
博士課程の指導教員	シャフィ・ゴールドワッサー

サリル・ヴァダンはアメリカのコンピュータ科学者である。彼はハーバード大学のコンピュータサイエンスと応用数学のヴィッキー・ジョセフ教授である。^[1] 1995年にハーバード大学で数学とコンピュータサイエンスの学士号を取得した後、1999年にマサチューセッツ工科大学で応用数学の博士号を取得し、そこでシャフィ・ゴールドワッサーに指導を受けた。^{[2]彼の研究は}計算複雑性理論と暗号学のインターフェースを中心にしており、擬似乱数とゼロ知識証明のトピックに焦点を当てている。オメル・ラインゴールドおよびアヴィ・ウィグダーソンとのジグザグ積に関する研究は2009年のゲーデル賞を受賞した。^[3]

彼の研究の主な貢献の 1 つは、ジグザグ積と呼ばれる新しいタイプのグラフ積です。

大きなグラフと小さなグラフの積をとると、結果のグラフは、そのサイズを大きなグラフから、その次数を小さなグラフから、その拡張プロパティを両方から (大まかに) 継承します。反復により、1 つの定数サイズの拡張から始めて、あらゆるサイズの定数次数の拡張の単純で明示的な構築が得られます。

ジグザグ積の特性を直観的に理解し、簡単に分析するためには、拡張器を「エントロピー波」の伝播器として機能する関数と見なすことが重要です。拡張器は、エントロピーが 1 つの領域に集中している確率分布を、その集中が分散している分布に変換します。この観点から、グラフ積は、このような 2 つの波の建設的な干渉を可能にします。

この積の変形は抽出器に適用することができ、シード長が ソースのエントロピー不足（長さではなく）のみに（多重）対数的に依存し、高最小エントロピーソースのエントロピーをほぼすべて抽出する最初の明示的抽出器が得られます。これらの高最小エントロピー抽出器には、"固有値境界" を上回る最初の定数次数明示的エクスパンダーなど、いくつかの興味深い用途があります。

ヴァダンは、ラインゴールドの画期的な結果に続いて、無向ST連結性問題に対する別の簡略化されたアプローチ^[4]も考案しました。また、ジグザグ積は、オメル・ラインゴールドによるSL = Lの証明にも役立ちました。

この分野における彼の研究は、複雑性理論の手法を用いてゼロ知識証明の威力と限界を理解することです。Oded GoldreichおよびAmit Sahaiとの一連の論文で、彼らは統計的ゼロ知識証明を持つ問題のクラス SZK を徹底的に理解し、クラス SZK を特徴づけ、SZK がさまざまな操作に対して閉じていることを証明しました。最近の彼の研究は、SZK クラスの範囲を超えたゼロ知識証明に取り組むことでした。

彼はLu 、Omer Reingold、Avi Wigdersonとともに、 「定数倍まで最適」な ランダム性抽出器を初めて構築し、このテーマに関する 10 年間の研究で画期的な成果を達成しました。

彼は、トレヴィサン、ザッカーマン、カンプ、ラオとともに、（未知の）効率的なアルゴリズムによって生成されたランダム ソースであるサンプリング可能なソースからランダム性を抽出する（およびデータ圧縮する）理論を開発しました。

ヴァダンは2018年に「計算複雑性と暗号技術の進歩、および理論計算機科学に対する国民の支援の促進」によりACMフェローに選出された。 ^[5]

• ハーバード大学のサリル・ヴァダンのホームページ。