Шмуэль Сафра | |
|---|---|
| Родившийся | 1962 г. |
| Альма-матер | Кандидат наук. Институт науки Вейцмана 1990 г. |
| Награды | Премия Гёделя |
| Научная карьера | |
| Поля | Информатика , теория сложности |
| Учреждения | Тель-авивский университет |
| Докторант | Амир Пнуэли |
Шмуэль Сафра ( иврит : שמואל ספרא ) - израильский ученый-компьютерщик. Он профессор компьютерных наук в Тель-Авивском университете , Израиль . Он родился в Иерусалиме .
Исследования в области Сафры включает теорию сложности и теорию автоматов . Его работа в области теории сложности включает в себя классификацию проблем аппроксимации, демонстрирующую их NP-трудность даже для слабых факторов аппроксимации, а также теорию вероятностно проверяемых доказательств (PCP) и теорему PCP , которая дает более сильные характеристики класса NP с помощью доказательство членства, которое можно проверить, прочитав только постоянное количество его битов.
Его работа по теории автоматов расследует детерминизацию и комплементирование конечных автоматов над бесконечными строками, в частности, сложность такого перевода для Бюхи автоматов , Streett автоматов и Рабин автоматов .
В 2001 году Сафра получил премию Геделя в области теоретической информатики за свои работы «Интерактивные доказательства и твердость аппроксимирующих клик» и «Вероятностная проверка доказательств: новая характеристика NP».
См. Также [ править ]
Внешние ссылки [ править ]
