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