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

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

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

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

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

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

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

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

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

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

  • Керівники

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

    Хвости

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

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

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

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

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

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

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

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

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

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

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

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

• «Weddings: Kathryn Farley, Richard Lipton», The New York Times, 5 June 2016.

• Персональний блог «Загублений лист Геделя і P = NP»