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

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

Річард Ліптон
Народився	6 вересня 1946(1946-09-06)^[1](77 років)
Місце проживання	Атланта
Країна	США
Діяльність	інформатик, викладач університету, математик
Alma mater	Карнегі-Меллон
Заклад	Технологічний інститут Джорджії
Науковий ступінь	докторський ступінь^[2]
Науковий керівник	^d
Аспіранти, докторанти	Аві Віґдерсон Ден Боне ^d^[3] ^d^[3] ^d^[3] ^d^[3] ^d^[3] ^d^[3] ^d^[3] Тімоті Бадд^[3] ^d^[3] ^d^[3] ^d^[3] ^d^[3] ^d^[3] ^d^[3] ^d^[3] ^d
Членство	Американська академія мистецтв і наук Національна інженерна академія США Association for Computing Machinery^[4]
Нагороди	Грант Ґуґґенгайма премія Кнута (2014) ^d (1997)
Особ. сторінка	scs.gatech.edu/people/richard-lipton

У Вікіпедії є статті про інших людей із прізвищем Ліптон.

Кар'єра

У 1968 році, Річард Ліптон отримав ступінь бакалавра математики у Західному резервному університеті Кейса (англ. Case Western Reserve University). У 1973 році він отримав ступінь доктора філософії в Університеті Карнегі-Меллон. Його науковим керівником з написання дисертації «Про первісні системи синхронізації» був Девід Парнас.

Після закінчення університету Р.Ліптон викладав у Єльському університеті (1973—1978 рр.) та в Університет Каліфорнії в Берклі (1978—1980 рр.), а потім у Принстонському університеті (1980—2000 рр.) Починаючи з 2000 року, Ліптон працює в Технологічному інституті Джорджії (англ. Georgia Tech).

Перебуваючи в Принстоні, Ліптон працював в галузі обчислень ДНК. З 1996 року, Ліптон є головним науковим консультантом в компанії Telcordia Technologies.

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

У 1980 році разом з Річардом М. Карпом, Ліптон довів, що якщо задача здійсненності булевих формул (SAT) може бути вирішена за допомогою логічних схем з поліноміальним числом логічних вентилів, то поліноміальна ієрархія переходить до свого другого рівня.

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

Демонстрація того, що програма P має якусь властивість — це простий процес, якщо дії всередині програми є безперебійними. Проте, коли дія переривна, Літптон показав, що за допомогою типу скорочення та аналізу можна показати, що зменшена програма має таку властивість тоді і тільки тоді, коли оригінальна програма має цю властивість. Якщо скорочення здійснюється шляхом трактування переривних операцій як однієї великої безперервної дії, навіть за цих спокійних умов властивості можна довести для програми P. Таким чином, доведення правильності паралельної системи можна значно спростити.

Безпека баз даних

Річард Ліптон вивчав і створював моделі безпеки бази даних щодо того, як і коли обмежувати запити, зроблені користувачами бази даних, щоб приватна або секретна інформація нікуди не просочувалась. Навіть коли користувачі обмежено лише операції зчитування з базою даних, захищена інформація може бути під загрозою. Наприклад, запит до бази даних пожертв на виборчі кампанії може дозволити користувачеві виявити окремі пожертви політичним кандидатам або організаціям. Якщо користувачеві надано доступ до середніх показників даних та необмежений доступ до запитів, користувач може використовувати властивості цих середніх значень для отримання інформації, яку він не мав би отримувати. Вважається, що ці запити мають велике «перекриття», створюючи небезпеку. Завдяки обмеженню «перекриття» та кількості запитів можна досягти захищеної бази даних.

Онлайн планування

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

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

• На 1-інтервал, фліп монета

  • Керівники

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

    Хвости

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

• Для інтервалу k приймайте, коли це можливо.

Знову ж таки, це 2-розмірний алгоритм є сильно конкурентним. Потім узагальнений алгоритм k-розміру, подібний до алгоритму 2-розміру, виявляється O(log${\displaystyle \vartriangle ^{1+\epsilon }}$) — конкурентоспроможний.

Перевірка програми

Річард Ліптон показав, що рандомізоване тестування може бути доказово корисним, враховуючи проблему, яка задовольняє певні властивості. Доведення правильності програми є однією з найважливіших проблем, що виникають в інформатиці. Зазвичай при рандомізованому тестуванні, щоб досягти 1/1000 ймовірності помилки, потрібно виконати 1000 тестів. Однак Ліптон показує, що якщо проблема має «легкі» підрозділи, повторне тестування «чорної скриньки» може досягти рівня помилок cr, при цьому константа менше 1, а r — кількість тестів. Отже, ймовірність помилки дорівнює нулю експоненційно швидко, коли r зростає.

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

• Обробка сигналів: швидке перетворення Фур'є (FFT) та інші функції, що сильно розпаралелюються, важко вручну перевірити результати при написанні в коді, такому як FORTRAN, тому спосіб швидкої перевірки правильності дуже бажаний.
• Функцій над скінченними полями та постійними: припустимо, що ${\displaystyle f(x_{1},\dots ,x_{n})}$ — це поліном над скінченним полем розміром М З q > deg(ƒ) + 1. Тоді ѓ довільно перевіряється порядком deg(ƒ) + 1 над основою функції, що включає лише додавання. Мабуть, найважливішим додатком із цього є здатність ефективно перевіряти правильність. Косметично подібний до детермінанта, перманент дуже важко перевірити правильність, але навіть такий тип проблем задовольняє обмеження. Цей результат навіть призвів до проривів інтерактивних систем доказу Карлоффа-Нісана та Шаміра, включаючи результат IP = PSPACE.

Ігри з простими стратегіями

У галузі теорії ігор, зокрема некооперативних ігор, Ліптон спільно з Е. Маркакісом та А. Мехтою довів  стратегій епсілон-рівноваги з підтримкою логарифмічного числа чистих стратегій. Крім того, виграш від таких стратегій може приблизно наблизити виграш від точних рівноваг Неша. Обмежений (логарифмічний) розмір опори забезпечує природний квазіполіноміальний алгоритм для обчислення епсилон-рівноваг.

Оцінка розміру запиту

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

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

ДеМілло, Ліптон та Алан Перліс піддали критиці ідею офіційної перевірки програм і аргументували це:

• Формальні перевірки в галузі інформатики не будуть відігравати тієї ж ключової ролі, як докази в математиці.
• Відсутність безперервності, неминучість змін та складність специфікації реальних програм ускладнюють формальну перевірку програм, яку важко виправдати та керувати нею.

Нагороди та почесні звання

• Грант Гуггенхайма, 1981
• Членство в Асоціації обчислювальної техніки, 1997
• член Національної академії інженерних наук
• Премія Кнута, 2014

Див. також

• Теорема про планарне розбиття

Джерела

• «Weddings: Kathryn Farley, Richard Lipton [ 7 квітня 2018 у Wayback Machine.]», The New York Times, 5 June 2016.

Посилання

• Персональний блог «Загублений лист Геделя і P = NP» [ 14 березня 2018 у Wayback Machine.]

Примітки

1. SNAC — 2010.
   d:Track:Q29861311
2. Deutsche Nationalbibliothek Record #142572888 // Gemeinsame Normdatei — 2012—2016.
   d:Track:Q27302d:Track:Q36578
3. Математичний генеалогічний проєкт — 1997.
   d:Track:Q829984
4. https://awards.acm.org/fellows/award-recipients
5. Lipton, R (1975) «Reduction: a method of proving properties of parallel programs» [ 10 травня 2020 у Wayback Machine.], Communications of the ACM 18(12)
6. Lipton, R (1979) «Secure databases: protection against user influence» [ 17 червня 2010 у Wayback Machine.] «ACM Transactions on Database Systems» 4(1)
7. Lipton, R (1994). Online interval scheduling. Symposium on Discrete Algorithms. с. 302—311. CiteSeerX 10.1.1.44.4548.
8. Lipton, R (1991) «New Directions in Testing», «DIMACS Distributed Computing and Cryptography» Vol. 2 page: 191
9. Richard Lipton, Evangelos Markakis, Aranyak Mehta (2007) «Playing Games with Simple Strategies», «EC '03: Proceedings of the 4th ACM conference on Electronic commerce», «ACM»
10. Richard J. Lipton, Jeffrey F. Naughton (1990) «Query Size Estimation By Adaptive Sampling», «PODS '90: Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems»
11. Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider (1990) «SIGMOD '90: Proceedings of the 1990 ACM SIGMOD international conference on Management of data»
12. Richard A. DeMillo, Richard J. Lipton, Alan J. Perlis (1979) «Social processes and proofs of theorems and programs», Communications of the ACM, Volume 22 Issue 5"
13. . Association for Computing Machinery. 15 вересня 2014. Архів оригіналу за вересень 20, 2014. Процитовано квітень 7, 2018.