Ричард Липтон - Richard Lipton

Ричард Джей Липтон (родился 6 сентября 1946 г.) Американец -Южноафриканский специалист в области информатики кто работал в теория информатики, криптография, и ДНК-вычисления. Липтон - заместитель декана по исследованиям, профессор и заведующий кафедрой вычислительной техники Фредерика Г. Стори в вычислительном колледже Технологический институт Джорджии.

Карьера

В 1968 году Липтон получил степень бакалавра в математика из Кейс Вестерн Резервный университет. В 1973 году он получил Кандидат наук. из Университет Карнеги Меллон; его диссертацию под руководством Давид Парнас, имеет право О примитивных системах синхронизации. После выпуска Липтон преподавал в Йель 1973–1978, на Беркли 1978–1980, а затем в Принстон 1980–2000 гг. С 2000 года Lipton работает в Технологический институт Джорджии. В Принстоне Липтон работал в области ДНК-вычисления. С 1996 года Липтон был главным научным консультантом в Telcordia.

Теорема Карпа – Липтона

В 1980 г. вместе с Ричард М. Карп, Липтон доказал, что если СИДЕЛ может быть решена Булевы схемы с полиномиальным числом логические ворота, то полиномиальная иерархия рушится до второго уровня.

Параллельные алгоритмы

Показать, что программа P имеет какое-то свойство, является простым процессом, если действия внутри программы непрерывны. Однако, когда действие можно прервать, Липтон показал, что посредством определенного типа редукции и анализа можно показать, что сокращенная программа обладает этим свойством тогда и только тогда, когда исходная программа имеет это свойство.^[2] Если сокращение выполняется путем обработки прерываемых операций как одного большого непрерывного действия, даже с этими расслабленными условиями свойства могут быть доказаны для программы P. Таким образом, доказательства корректности параллельной системы часто могут быть значительно упрощены.

Безопасность базы данных

Липтон изучал и создавал модели безопасности баз данных о том, как и когда ограничивать запросы пользователей базы данных, чтобы не допустить утечки частной или секретной информации.^[3] Даже когда пользователь ограничен только операциями чтения в базе данных, защищенная информация может оказаться под угрозой. Например, запрос к базе данных пожертвований на кампании может позволить пользователю обнаружить отдельные пожертвования политическим кандидатам или организациям. Если получить доступ к средним данным и неограниченный доступ к запросам, пользователь может использовать свойства этих средних значений для получения незаконной информации. Считается, что эти запросы имеют большое «перекрытие», что создает угрозу. Ограничивая «перекрытие» и количество запросов, можно обеспечить безопасность базы данных.

Онлайн-планирование

Ричард Липтон и Эндрю Томкинс представили рандомизированный онлайн-алгоритм планирования интервалов, версия 2-го размера является весьма конкурентоспособной, а k-размер версии достигает O (журнал${displaystyle vartriangle ^ {1 + epsilon}}$), а также демонстрирует теоретическую нижнюю границу O (log${displaystyle vartriangle}$).^[4] Этот алгоритм использует частную монету для рандомизации и «виртуальный» выбор, чтобы обмануть средний противник.

Получив представление о событии, пользователь должен решить, включать ли это событие в расписание. Виртуальный алгоритм 2-го размера описывается тем, как он реагирует на 1-интервальный или k-интервалы, предъявляемые противником:

• Для 1-го интервала подбросьте честно.

  • Головы

    Возьмите интервал

    Хвосты

    «Практически» беру интервал, но ничего не получается. Не делайте коротких интервалов в течение следующей 1 единицы времени.

• Для k-интервал, бери по возможности.

Опять же, этот алгоритм 2-го размера демонстрирует сильнуюконкурентный. Обобщенный kалгоритм -size, который похож на алгоритм 2-размера, затем отображается как O (log${displaystyle vartriangle ^ {1 + epsilon}}$)-конкурентный.

Проверка программы

Липтон показал, что рандомизированное тестирование может оказаться полезным, если проблема удовлетворяет определенным свойствам.^[5] Доказательство правильность программы - одна из важнейших проблем информатики. Как правило, при рандомизированном тестировании для достижения вероятности ошибки 1/1000 необходимо выполнить 1000 тестов. Однако Липтон показывает, что если проблема имеет "легкие" части, повторное тестирование методом черного ящика может быть достигнуто. c^р коэффициент ошибок, с c константа меньше 1 и р количество тестов. Следовательно, вероятность ошибки экспоненциально стремится к нулю быстро как р растет.

Этот метод полезен для проверки правильности многих типов проблем.

• Обработка сигналов: быстрое преобразование Фурье (БПФ) и другие функции с высокой степенью распараллеливания трудно проверить результаты вручную, если они написаны в коде, например FORTRAN, поэтому очень желателен способ быстрой проверки правильности.
• Функции над конечными полями и перманентом: предположим, что ${displaystyle f (x_ {1}, dots, x_ {n})}$ является многочленом над конечным полем размера q с q > град (ƒ) + 1. потом ƒ случайным образом проверяется по порядку град (ƒ) + 1 над функциональной базой, включающей только сложение. Возможно, самое важное приложение из этого - возможность эффективно проверять правильность постоянный. Косметически подобный определителю, перманент очень сложно проверить на правильность, но даже этот тип проблемы удовлетворяет ограничениям. Этот результат даже привел к прорыву интерактивные системы доказательства Карлофф-Нисан и Шамир, включая результат IP = PSPACE.

Игры с простыми стратегиями

В районе теория игры, а точнее некооперативные игры, Липтон совместно с Э. Маркакисом и А. Мехтой доказали^[6] Существование эпсилон-равновесие стратегии с поддержкой логарифмической по количеству чистые стратегии. Кроме того, выигрыш таких стратегий может эпсилон-аппроксимировать выигрыши точных Равновесия Нэша. Ограниченный (логарифмический) размер опоры обеспечивает естественный квазиполиномиальный алгоритм для вычисления эпсилон-равновесие.

Оценка размера запроса

Липтон и Дж. Нотон представили алгоритм адаптивной случайной выборки для запросов к базе данных.^[7][8] который применим к любому запросу, ответы на который можно разбить на непересекающиеся подмножества^{[требуется разъяснение ]}. В отличие от большинства алгоритмов оценки выборки, которые статически определяют количество необходимых выборок, их алгоритм определяет количество выборок на основе размеров выборок и стремится поддерживать постоянное время выполнения (в отличие от линейного по количеству выборок).

Формальная проверка программ

DeMillo, Липтон и Perlis^[9] критиковал идею формальной верификации программ и утверждал, что

• Формальные проверки в информатике не будут играть такую ​​же ключевую роль, как доказательства в математике.
• Отсутствие непрерывности, неизбежность изменений и сложность спецификации реальных программ сделают формальную верификацию программ трудной для обоснования и управления.

Многосторонние протоколы

Чандра, Ферст и Липтон^[10] обобщил понятие протоколов двусторонней связи до протоколов многосторонней связи. Они предложили модель, в которой совокупность процессов (${displaystyle P_ {0}, P_ {1}, ldots, P_ {k-1}}$) имеют доступ к набору целых чисел (${displaystyle a_ {0}}$, ${displaystyle a_ {1}, ldots, a_ {k-1}}$) кроме одного из них, так что ${displaystyle P_ {i}}$ отказано в доступе к ${displaystyle a_ {i}}$. Этим процессам разрешено взаимодействовать для достижения консенсуса по предикату. Они изучили коммуникационную сложность этой модели, определяемую как количество битов, передаваемых между всеми процессами. В качестве примера они изучили сложность k-партийный протокол для точно-N (сделай все ${displaystyle a_ {i}}$Суммируется до N?) И получил нижнюю границу с помощью метода мозаики. Далее они применили эту модель для изучения общих программ ветвления и получили оценку снизу по времени для программ ветвления в постоянном пространстве, которые вычисляют точно-N.

Компромисс времени / пространства SAT

У нас нет возможности доказать, что Проблема логической выполнимости (часто сокращенно SAT), то есть НП-полный, требует экспоненциального (или, по крайней мере, суперполиномиального) времени (это знаменитый P против проблемы NP ) или линейное (или, по крайней мере, супер-логарифмическое) пространство для решения. Однако в контексте компромисс между пространством и временем, можно доказать, что SAT не может быть вычислен, если мы применяем ограничения как для времени, так и для пространства. Л. Фортноу, Липтон, Д. ван Мелкебек и А. Виглас^[11] доказал, что SAT не может быть вычислен машиной Тьюринга, которая берет не более O (п^1.1) шагов и не более O (п^0.1) ячеек своих лент чтения-записи.

Награды и отличия

• Сотрудник Гуггенхайма, 1981
• Парень из Ассоциация вычислительной техники, 1997
• член Национальная инженерная академия
• Приз Кнута победитель, 2014^[12]

Смотрите также

• SL (сложность)
• Модель защиты от взятия гранта
• Теорема о плоском сепараторе

Примечания

дальнейшее чтение

• "Свадьбы: Кэтрин Фарли, Ричард Липтон ", Нью-Йорк Таймс, 5 июня 2016 г.

внешняя ссылка

• Его личный блог «Потерянное письмо Гёделя и P = NP»