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

Ричард Липтон
Рожденный	Ричард Джей Липтон ( 1946-09-06 ) 6 сентября 1946 г.
Альма-матер	Карнеги-Меллон
Известный	Теорема Карпа – Липтона и теорема о плоском сепараторе
Награды	Премия Кнута (2014)
Научная карьера
Поля	Информатика
Учреждения	Йельский университет Беркли Принстон Технологический институт Джорджии
Диссертация	О примитивных системах синхронизации   (1973)
Докторантура	Дэвид Парнас
Докторанты	Дэн Бонех Виджая Рамачандран Ави Вигдерсон

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

Карьера

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

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

Основная статья: теорема Карпа – Липтона

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

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

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

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

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

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

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

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

• В течение 1 интервала подбросьте честную монету.

  • Руководители

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

    Решка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Награды и почести

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

См. также

• СЛ (сложность)
• Модель защиты по принципу «возьми грант»
• Теорема о плоском сепараторе

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

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

Внешние ссылки

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