Ричард Липтон

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

Карьера [ править ]

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

Теорема Карпа – Липтона [ править ]

В 1980 году вместе с Ричардом М. Карпом Липтон доказал, что если SAT может быть решена с помощью булевых схем с полиномиальным числом логических элементов , то полиномиальная иерархия схлопывается до второго уровня.

Параллельные алгоритмы [ править ]

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

Безопасность базы данных [ править ]

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

Онлайн-расписание [ править ]

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

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

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

  • Головы

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

    Хвосты

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

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

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

Проверка программы [ править ]

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

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

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

Игры с простыми стратегиями [ править ]

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

Оценка размера запроса [ править ]

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

Формальная проверка программ [ править ]

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

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

Многосторонние протоколы [ править ]

Чандра, Ферст и Липтон ^[10] обобщили понятие протоколов двусторонней связи на протоколы многосторонней связи. Они предложили модель, в которой набор процессов ( ) имеет доступ к набору целых чисел ( , ), кроме одного из них, поэтому доступ к нему запрещен . Этим процессам разрешено взаимодействовать, чтобы прийти к консенсусу по предикату. Они изучили коммуникационную сложность этой модели, определяемую как количество битов, передаваемых между всеми процессами. В качестве примера они изучили сложность k- стороннего протокола для Exactly- N (do all${\ 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}}$${\ displaystyle a_ {i}}$суммируются до N?) и получили нижнюю оценку с помощью метода мозаики. Далее они применили эту модель для изучения общих программ ветвления и получили оценку снизу по времени для программ ветвления в постоянном пространстве, которые вычисляют Exactly- N .

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

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

Награды и награды [ править ]

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

См. Также [ править ]

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

Заметки [ править ]

Дальнейшее чтение [ править ]

• « Свадьбы: Кэтрин Фарли, Ричард Липтон », The New York Times , 5 июня 2016 г.

Внешние ссылки [ править ]

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