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

Річард Ліптон
Народився6 вересня 1946(1946-09-06)[1] Редагувати інформацію у Вікіданих (78 років)
Місце проживанняАтланта
Країна США Редагувати інформацію у Вікіданих
Діяльністьінформатик, викладач університету, математик
Alma materКарнегі-Меллон
ЗакладТехнологічний інститут Джорджії Редагувати інформацію у Вікіданих
Науковий ступіньдокторський ступінь[2] Редагувати інформацію у Вікіданих
Науковий керівникDavid Parnasd Редагувати інформацію у Вікіданих
Аспіранти, докторантиАві Віґдерсон Редагувати інформацію у Вікіданих
Ден Боне Редагувати інформацію у Вікіданих
Vijaya Ramachandrand[3] Редагувати інформацію у Вікіданих
Chee-Keng Yapd[3] Редагувати інформацію у Вікіданих
Daniel Philip Loprestid[3] Редагувати інформацію у Вікіданих
Anastasios Viglasd[3] Редагувати інформацію у Вікіданих
Benjamin Brandon Gumd[3] Редагувати інформацію у Вікіданих
Arvin R. Parkd[3] Редагувати інформацію у Вікіданих
James Harold Shawd[3] Редагувати інформацію у Вікіданих
Тімоті Бадд[3] Редагувати інформацію у Вікіданих
Hana Galperind[3] Редагувати інформацію у Вікіданих
Gopalakrishnan Vijayand[3] Редагувати інформацію у Вікіданих
Stephen C. Northd[3] Редагувати інформацію у Вікіданих
Dimitrios Serpanosd[3] Редагувати інформацію у Вікіданих
Krishnaswamy Balasubramaniand[3] Редагувати інформацію у Вікіданих
Danupon Nanongkaid[3] Редагувати інформацію у Вікіданих
Shiva Kintalid[3] Редагувати інформацію у Вікіданих
Nisheeth K. Vishnoid Редагувати інформацію у Вікіданих
ЧленствоАмериканська академія мистецтв і наук Редагувати інформацію у Вікіданих
Національна інженерна академія США Редагувати інформацію у Вікіданих
Association for Computing Machinery[4] Редагувати інформацію у Вікіданих
Нагороди
Особ. сторінкаscs.gatech.edu/people/richard-lipton Редагувати інформацію у Вікіданих
У Вікіпедії є статті про інших людей із прізвищем Ліптон.

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

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

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

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

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

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

Див. також

Джерела

Посилання

Примітки

  1. ↑ SNAC — 2010.
  2. ↑ Deutsche Nationalbibliothek Record #142572888 // Gemeinsame Normdatei — 2012—2016.
  3. ↑ а б в г д е ж и к л м н п р с Математичний генеалогічний проєкт — 1997.
  4. ↑ https://awards.acm.org/fellows/award-recipients
  5. ↑ 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»
  6. ↑ Richard J. Lipton, Jeffrey F. Naughton, Donovan A. Schneider (1990) «SIGMOD '90: Proceedings of the 1990 ACM SIGMOD international conference on Management of data»
  7. ↑ ACM Awards Knuth Prize to Pioneer for Advances in Algorithms and Complexity Theory. Association for Computing Machinery. 15 вересня 2014. Архів оригіналу за вересень 20, 2014. Процитовано квітень 7, 2018.