Ричард Джей Lipton (родился 6 сентября 1946) является американским - южноафриканский ученым , который работал в теории науки компьютера , криптография , и ДНК вычисления . Липтон - заместитель декана по исследованиям, профессор и заведующий кафедрой вычислительной техники вычислительного колледжа Технологического института Джорджии .
Ричард Липтон | |
---|---|
Родившийся | Ричард Джей Липтон 6 сентября 1946 г. |
Альма-матер | Университет Карнеги-Меллона |
Известен | Карп-Lipton теорема и плоская Сепаратор теорема |
Награды | Приз Кнута (2014) |
Научная карьера | |
Поля | Информатика |
Учреждения | Йельский университет Беркли, Принстон, Джорджия, Технологический институт |
Тезис | О примитивных системах синхронизации (1973) |
Докторант | Дэвид Парнас [1] |
Докторанты | Дэн Боне Ави Вигдерсон |
Карьера
В 1968 году Липтон получил степень бакалавра математики в Университете Кейс Вестерн Резерв . В 1973 году он получил докторскую степень. из Университета Карнеги-Меллона ; его диссертация, под руководством Дэвида Парнаса , озаглавлена « О примитивных системах синхронизации» . После окончания университета Липтон преподавал в Йельском университете в 1973–1978 годах, в Беркли в 1978–1980 годах, а затем в Принстоне в 1980–2000 годах. С 2000 года Липтон работает в Технологическом институте Джорджии . В Принстоне Липтон работал в области вычислений ДНК . С 1996 года Липтон был главным научным консультантом Telcordia .
Теорема Карпа – Липтона
В 1980 году вместе с Ричардом М. Карпом Липтон доказал, что если SAT может быть решена с помощью булевых схем с полиномиальным числом логических элементов , то полиномиальная иерархия схлопывается до второго уровня.
Параллельные алгоритмы
Показать, что программа P имеет какое-либо свойство, является простым процессом, если действия внутри программы непрерывны. Однако, когда действие можно прервать, Липтон показал, что с помощью некоторого типа редукции и анализа можно показать, что сокращенная программа обладает этим свойством тогда и только тогда, когда исходная программа имеет это свойство. [2] Если сокращение выполняется путем обработки прерываемых операций как одного большого непрерывного действия, даже с этими ослабленными условиями свойства могут быть доказаны для программы P. Таким образом, доказательства корректности параллельной системы часто могут быть значительно упрощены.
Безопасность базы данных
Липтон изучал и создавал модели безопасности баз данных о том, как и когда ограничивать запросы, сделанные пользователями базы данных, чтобы не допустить утечки частной или секретной информации. [3] Даже когда пользователь ограничен только операциями чтения в базе данных, защищенная информация может оказаться под угрозой. Например, запрос к базе данных пожертвований кампании может позволить пользователю обнаружить отдельные пожертвования политическим кандидатам или организациям. Если получить доступ к средним данным и неограниченный доступ к запросам, пользователь может использовать свойства этих средних значений для получения незаконной информации. Считается, что эти запросы имеют большое «перекрытие», что создает небезопасность. Ограничивая «перекрытие» и количество запросов, можно обеспечить безопасность базы данных.
Онлайн-расписание
Ричард Липтон и Эндрю Томкинс представили рандомизированный алгоритм онлайн-планирования интервалов , при этом версия с размером 2 является сильно конкурентной, а версия с размером k достигает O (log), а также демонстрирует теоретическую нижнюю границу O (log). [4] Этот алгоритм использует частную монету для рандомизации и «виртуальный» выбор, чтобы обмануть среднего противника .
Получив представление о событии, пользователь должен решить, следует ли включать это событие в расписание. Виртуальный алгоритм 2-го размера описывается тем, как он реагирует на 1-интервал или k -интервалы , представленные противником:
- Для 1-го интервала подбросьте честно.
- Головы
- Возьмите интервал
- Хвосты
- «Практически» беру интервал, но ничего не получается. Не делайте коротких интервалов в течение следующей 1 единицы времени.
- Для k- интервала по возможности используйте.
Опять же, этот алгоритм двух размеров демонстрирует высокую конкурентоспособность . Затем показано, что обобщенный алгоритм размера k , который похож на алгоритм размера 2, равен O (log)-конкурентоспособный.
Проверка программы
Липтон показал, что рандомизированное тестирование может быть доказуемо полезным, если задача удовлетворяет определенным свойствам. [5] Доказательство правильности программы - одна из важнейших задач информатики. Обычно при рандомизированном тестировании для достижения вероятности ошибки 1/1000 необходимо выполнить 1000 тестов. Однако Липтон показывает, что если проблема имеет "легкие" части, повторное тестирование методом черного ящика может достичь коэффициента ошибок c r , где c - константа меньше 1, а r - количество тестов. Следовательно, вероятность ошибки экспоненциально быстро стремится к нулю с ростом r .
Этот метод полезен для проверки правильности многих типов проблем.
- Обработка сигналов: быстрое преобразование Фурье (БПФ) и другие функции с высокой степенью распараллеливания затрудняют ручную проверку результатов при написании в таком коде, как FORTRAN , поэтому очень желателен способ быстрой проверки правильности.
- Функции над конечными полями и перманентом: предположим, что является многочленом над конечным полем размера q с q > deg ( ƒ ) + 1 . Тогда ƒ тестируемо случайным образом порядка deg ( ƒ ) + 1 над функциональным базисом, включающим только сложение. Пожалуй, самое важное применение из этого - возможность оперативно проверить правильность перманента . Косметически подобный определителю, перманент очень сложно проверить на правильность, но даже этот тип проблемы удовлетворяет ограничениям. Этот результат даже привел к прорыву в интерактивных системах доказательства Karloff-Nisan и Shamir, включая результат IP = PSPACE .
Игры с простыми стратегиями
В области теории игр , в частности, некооперативных игр , Липтон вместе с Э. Маркакисом и А. Мехтой доказали [6] существование эпсилон-равновесных стратегий с опорным логарифмическим числом чистых стратегий . Кроме того, выигрыш таких стратегий может эпсилон-аппроксимировать выигрыши точного равновесия Нэша . Ограниченный (логарифмический) размер опоры обеспечивает естественный квазиполиномиальный алгоритм для вычисления эпсилон-равновесий .
Оценка размера запроса
Липтон и Дж. Нотон представили алгоритм адаптивной случайной выборки для запросов к базе данных [7] [8], который применим к любому запросу, ответы на который можно разделить на непересекающиеся подмножества [ требуется пояснение ] . В отличие от большинства алгоритмов оценки выборки, которые статически определяют количество необходимых выборок, их алгоритм определяет количество выборок на основе размеров выборок и стремится поддерживать постоянное время выполнения (в отличие от линейного по количеству выборок).
Формальная проверка программ
Де Милло , Липтон и Перлис [9] критиковали идею формальной верификации программ и утверждали, что
- Формальные проверки в информатике не будут играть такую же ключевую роль, как доказательства в математике.
- Отсутствие непрерывности, неизбежность изменений и сложность спецификации реальных программ сделают формальную верификацию программ трудной для обоснования и управления.
Многосторонние протоколы
Чандра, Ферст и Липтон [10] обобщили понятие протоколов двусторонней связи на протоколы многосторонней связи. Они предложили модель, в которой совокупность процессов () имеют доступ к набору целых чисел (, ) кроме одного из них, так что отказано в доступе к . Этим процессам разрешено взаимодействовать, чтобы прийти к консенсусу по предикату. Они изучили коммуникационную сложность этой модели, определяемую как количество битов, передаваемых между всеми процессами. В качестве примера они изучили сложность k- стороннего протокола для Exactly- N (do allсуммируются до N?) и получили нижнюю оценку с помощью метода мозаики. Далее они применили эту модель для изучения общих программ ветвления и получили оценку снизу по времени для программ ветвления в постоянном пространстве, которые вычисляют Exactly- N .
Компромисс времени / пространства SAT
У нас нет способа доказать, что проблема логической выполнимости (часто сокращенно SAT), которая является NP-полной , требует экспоненциального (или, по крайней мере, суперполиномиального) времени (это знаменитая проблема P по сравнению с NP ) или линейной (или минимум супер-логарифмического) места для решения. Однако в контексте компромисса между пространством и временем можно доказать, что SAT нельзя вычислить, если мы применяем ограничения как к времени, так и к пространству. Л. Фортноу, Липтон, Д. ван Мелкебек и А. Виглас [11] доказали, что SAT не может быть вычислен машиной Тьюринга, которая занимает не более O ( n 1,1 ) шагов и не более O ( n 0,1 ) ячеек его чтения. -записывать кассеты.
Награды и почести
- Сотрудник Гуггенхайма , 1981 г.
- Член в Ассоциации вычислительной техники , 1997
- член Национальной инженерной академии
- Лауреат Премии Кнута 2014 г. [12]
Смотрите также
- SL (сложность)
- Модель защиты от взятия гранта
- Теорема о плоском сепараторе
Заметки
- ^ Ричард Липтон в проекте математической генеалогии
- ^ Липтон, R (1975) "Редукция: метод доказательства свойств параллельных программ" , Сообщения ACM 18 (12)
- ^ Lipton, R (1979) «Защищенные базы данных: защита от влияния пользователя» , «Транзакции ACM в системах баз данных» 4 (1)
- Перейти ↑ Lipton, R (1994). Интервальное планирование онлайн . Симпозиум по дискретным алгоритмам . С. 302–311. CiteSeerX 10.1.1.44.4548 .
- ^ Lipton, R (1991) «Новые направления в тестировании», «Распределенные вычисления и криптография DIMACS», Vol. 2 стр .: 191
- ^ Ричард Липтон, Эвангелос Маркакис, Араньяк Мехта (2007) «Игра в игры с простыми стратегиями», «EC '03: Материалы 4-й конференции ACM по электронной коммерции», «ACM»
- ^ Ричард Дж. Липтон, Джеффри Ф. Нотон (1990) «Оценка размера запроса с помощью адаптивной выборки», «PODS '90: Материалы девятого симпозиума ACM SIGACT-SIGMOD-SIGART по принципам систем баз данных»
- ^ Ричард Дж. Липтон, Джеффри Ф. Нотон, Донован А. Шнайдер (1990) «SIGMOD '90: Материалы международной конференции ACM SIGMOD 1990 года по управлению данными»
- ^ Ричард А. ДеМилло, Ричард Дж. Липтон, Алан Дж. Перлис (1979) «Социальные процессы и доказательства теорем и программ», «Коммуникации ACM, том 22, выпуск 5»
- ↑ AK Chandra, ML Furst, and RJ Lipton (1983) «Многосторонние протоколы», «В STOC, страницы 94–99. ACM, 25–2»
- ^ Л. Fortnow, Р. Липтон, Д. ван Melkebeek и А. Viglas (2005) "Пространственно-временные нижние оценки выполнимости", «J. ACM, 52: 835-865, 2005. Prelim версия CCC«2000"
- ^ «ACM вручает премию Кнута пионеру в области алгоритмов и теории сложности» . Ассоциация вычислительной техники. 15 сентября, 2014. Архивировано из оригинального 20 сентября 2014 года.
дальнейшее чтение
- « Свадьбы: Кэтрин Фарли, Ричард Липтон », The New York Times , 5 июня 2016 г.
Внешние ссылки
- Его личный блог «Потерянное письмо Гёделя и P = NP»