シュムエル・サフラ

シュムエル（ムリ）サフラ（ヘブライ語：שמואל ספרא ）は、イスラエルのコンピュータ科学者です。イスラエルのテルアビブ大学でコンピュータサイエンスの教授を務めています。エルサレム生まれ。

サフラの研究分野には、計算量理論とオートマトン理論が含まれます。計算量理論における彼の研究には、近似問題の分類（近似の弱い因数に対してもNP 困難であることを示す）や、確率的に検証可能な証明（PCP）の理論、および一定数のビットのみを読み取ることで検証できる帰属証明を介してクラス NPのより強力な特徴付けを与えるPCP 定理が含まれます。

オートマトン理論に関する彼の研究は、無限文字列上の有限オートマトンの決定性と相補性、特にビュッヒ・オートマトン、ストリート・オートマトン、ラビン・オートマトンに対するそのような変換の複雑さを調査している。

2001 年、サフラは論文「対話型証明と近似クリークの困難性」および「証明の確率的チェック: NP の新しい特徴付け」により理論計算機科学のゲーデル賞を受賞しました。

参照