Рассел Импальяццо
(Перенаправлено с Рассела Грэма Импальяццо )
Рассел Грэм Импальяццо | |
|---|---|
 Рассел Импальяццо на семинаре DIMACS по криптографии, июль 2016 г. | |
| Альма-матер | Уэслианский университет ; Калифорнийский университет, Беркли |
| Известный | Результаты по теории сложности вычислений |
| Научная карьера | |
| Диссертация | Псевдослучайные генераторы для вероятностных алгоритмов и криптографии (1992) |
| Докторантура | Мануэль Блюм |
| Веб-сайт | https://cseweb.ucsd.edu//~russell/ |
Рассел Грэм Импальяццо [1] — профессор информатики Калифорнийского университета в Сан-Диего , специализирующийся на сложности вычислений . теории [2]
Образование
[ редактировать ]Импальяццо получил степень бакалавра математики в Уэслианском университете . [3] Он получил докторскую степень в Калифорнийском университете в Беркли в 1992 году. Его научным руководителем был Мануэль Блюм . [1] Он поступил на факультет UCSD в 1989 году. [4] работал там постдоком с 1989 по 1991 год. [3]
Взносы
[ редактировать ]Вклад Импальяццо в теорию сложности включает:
- построение генератора псевдослучайных чисел из любой односторонней функции , [5]
- его доказательство леммы XOR Яо с помощью «жестких наборов», [6]
- его доказательство нижней границы экспоненциального размера для Гильберта доказательств постоянной глубины принципа ячейки , [7]
- его работа о связи между вычислительной сложностью и дерандомизацией, [8] [9] [10] [11]
- и его работа над созданием бессемянных экстракторов с несколькими источниками. [12]
- утверждая гипотезу экспоненциального времени , согласно которой 3-SAT не может быть решена за субэкспоненциальное время по количеству переменных, [13] Эта гипотеза используется для вывода нижних границ алгоритмов в информатике . [14] [15]
Пять миров теории сложности
[ редактировать ]Импальяццо хорошо известен тем, что предложил «пять миров» теории сложности вычислений , отражающих возможные состояния мира вокруг проблемы P и NP . [16]
- Алгоритмика: P = NP;
- Эвристика: P не является NP, но проблемы NP в среднем решаемы;
- Пессиленд: есть NP-задачи, которые в среднем сложны, но нет односторонних функций ;
- Minicrypt: существуют односторонние функции, но криптографии с открытым ключом ; нет
- Криптомания: существует криптография с открытым ключом.
Понимание того, в каком мире мы живем, по-прежнему остается ключевым мотивирующим вопросом в теории сложности и криптографии. [17]
Награды
[ редактировать ]Импальяццо получил следующие награды:
- Награда за лучшую статью на конференции по сложности вычислений [3]
- Премия 2003 года за выдающуюся работу Общества промышленной и прикладной математики. [4]
- Премия за лучшую статью 2003 года на симпозиуме по теории вычислений. [4]
- назван стипендиатом Гуггенхайма 2004 года за работу над «эвристикой, сложностью доказательства и алгоритмическими методами» [4]
Ссылки
[ редактировать ]- ^ Jump up to: а б «Рассел Импальяццо - Проект математической генеалогии» . mathgenealogy.org . Проверено 30 августа 2021 г.
- ^ «Рассел Импальяццо» . cseweb.ucsd.edu . Проверено 30 августа 2021 г.
- ^ Jump up to: а б с «Рассел Импальяццо | Институт теории вычислений Саймонса» . simons.berkeley.edu . Проверено 30 августа 2021 г.
- ^ Jump up to: а б с д «Профиль факультета | Инженерная школа Джейкобса» . jacobsschool.ucsd.edu . Проверено 30 августа 2021 г.
- ^ Хостад, Йохан; Импальяццо, Рассел; Левин Леонид А.; Луби, Майкл (1999). «Псевдослучайный генератор любой односторонней функции» (PDF) . SIAM Journal по вычислительной технике . 28 (4): 1364–1396. дои : 10.1137/S0097539793244708 . ISSN 0097-5397 .
- ^ Импальяццо, Рассел (1995). «Жесткие дистрибутивы для довольно сложных задач» . Труды 36-й ежегодной конференции IEEE по основам компьютерных наук . Труды 36-й ежегодной конференции IEEE по основам компьютерных наук. стр. 538–545. дои : 10.1109/SFCS.1995.492584 . ISBN 0-8186-7183-1 . Проверено 30 августа 2021 г.
- ^ Бим, Пол; Импальяццо, Рассел; Крайчек, Ян; Питасси, Тонианн; Пудлак, Павел (1996). «Нижние границы Nullstellensatz Гильберта и доказательства высказываний» . Труды Лондонского математического общества . с3-73(1):1–26. дои : 10.1112/plms/s3-73.1.1 . ISSN 1460-244X .
- ^ Кабанец, Валентин; Импальяццо, Рассел (1 декабря 2004 г.). «Дерандомизация полиномиальных тестов на идентичность означает доказательство нижних границ схемы» . Вычислительная сложность . 13 (1): 1–46. дои : 10.1007/s00037-004-0182-6 . ISSN 1420-8954 . S2CID 12451799 .
- ^ Импальяццо, Рассел; Вигдерсон, Ави (4 мая 1997 г.). « P = BPP, если E требует экспоненциальных схем» . Материалы двадцать девятого ежегодного симпозиума ACM по теории вычислений - STOC '97 . Эль-Пасо, Техас, США: Ассоциация вычислительной техники. стр. 220–229. дои : 10.1145/258533.258590 . ISBN 978-0-89791-888-6 . S2CID 18921599 .
- ^ Импальяццо, Рассел (28 апреля 2003 г.). «Твердость как случайность: обзор всеобщей дерандомизации». arXiv : cs/0304040 .
- ^ Кармозино, Марко Л.; Импальяццо, Рассел; Кабанец, Валентин; Колоколова, Антонина (2015). Гарг, Навин; Янсен, Клаус; Рао, Ануп; Ролим, Хосе Д.П. (ред.). «Более тесная связь между дерандомизацией и нижними границами схемы» . Аппроксимация, рандомизация и комбинаторная оптимизация. Алгоритмы и методы (ПРИБЛИЗИТЕЛЬНО/СЛУЧАЙНО, 2015 г.) . Международные труды Лейбница по информатике (LIPIcs). 40 . Дагштуль, Германия: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 645–658. doi : 10.4230/LIPIcs.APPROX-RANDOM.2015.645 . ISBN 978-3-939897-89-7 .
- ^ Барак, Б.; Импальяццо, Р.; Вигдерсон, А. (2004). «Извлечение случайности с использованием нескольких независимых источников» . 45-й ежегодный симпозиум IEEE по основам информатики . стр. 384–393. дои : 10.1109/FOCS.2004.29 . ISBN 0-7695-2228-9 . S2CID 7063583 .
- ^ Импальяццо, Рассел; Патури, Рамамохан (1 марта 2001 г.). «О сложности k-SAT» . Журнал компьютерных и системных наук . 62 (2): 367–375. дои : 10.1006/jcss.2000.1727 . ISSN 0022-0000 .
- ^ Локштанов Даниил; Маркс, Даниэль; Саураб, Сакет (октябрь 2011 г.). «Нижние границы, основанные на гипотезе экспоненциального времени». Бюллетень EATCS : 41–71. CiteSeerX 10.1.1.942.6217 .
- ^ Уильямс, Вирджиния В. (2015). Сложность простых задач: обоснование сложности на популярных гипотезах, таких как сильная гипотеза экспоненциального времени (PDF) . 10-й международный симпозиум по параметризованным и точным вычислениям. стр. 17–29. doi : 10.4230/LIPIcs.IPEC.2015.17 .
- ^ Импальяццо, Рассел (17 апреля 1995 г.). «Личный взгляд на сложность среднего случая» .
- ^ Кларрайх, Эрика (18 апреля 2022 г.). «В какой вычислительной вселенной мы живем?» . Кванта .
