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