Райан Уильямс (ученый-компьютерщик)
Райан Уильямс | |
|---|---|
 Уильямс (ноябрь 2010 г.) | |
| Рожденный | 1979 (44–45 лет) |
| Национальность | Американский |
| Альма-матер | Корнелльский университет Университет Карнеги-Меллон |
| Научная карьера | |
| Поля | Теория сложности вычислений , Алгоритмы |
| Учреждения | Университет Карнеги-Меллон Исследовательский центр IBM в Альмадене Стэнфордский университет |
| Докторантура | Мануэль Блюм |
Ричард Райан Уильямс , известный как Райан Уильямс (1979 г.р.), — американский ученый-теоретик в области информатики, работающий в области теории сложности вычислений и алгоритмов .
Образование
[ редактировать ]Уильямс окончил Школу математики и естественных наук Алабамы , а затем получил степень бакалавра математики и информатики в Корнельском университете в 2001 году. [1] и степень доктора компьютерных наук в 2007 году в Университете Карнеги-Меллон под руководством Мануэля Блюма . [2] С 2010 по 2012 год он был членом теоретической группы исследовательского центра IBM в Альмадене . С осени 2011 по осень 2016 года он был профессором Стэнфордского университета. В январе 2017 года он поступил на факультет Массачусетского технологического института . [3]
Исследовать
[ редактировать ]Уильямс был членом программного комитета Симпозиума по теории вычислений в 2011 году и различных других конференций. Он выиграл награду Рона В. Бука за лучшую студенческую работу на конференции IEEE по вычислительной сложности в 2005 и 2007 годах. [4] и на награде за лучшую студенческую работу на Международном коллоквиуме по автоматам, языкам и программированию в 2004 году от Европейской ассоциации теоретической информатики . [5]
Результат Уильямса о том, что класс сложности NEXP не содержится в ACC. 0 получил награду за лучшую статью на конференции по вычислительной сложности в 2011 году. [6] Теоретик сложности Скотт Ааронсон назвал результат «одним из самых впечатляющих за десятилетие». [7] В 2024 году за эту работу Уильямс был удостоен премии Гёделя .
Уильямс также работал над вычислительной сложностью k -анонимности . [8]
Личная жизнь
[ редактировать ]Райан женат на Вирджинии Василевской Уильямс , также ученом-теоретике.
Избранные публикации
[ редактировать ]- Мейерсон, Адам; Уильямс, Райан (2004), «О сложности оптимальной k- анонимности», Труды двадцать третьего симпозиума ACM SIGMOD-SIGACT-SIGART по принципам систем баз данных (PODS '04) , Нью-Йорк, Нью-Йорк, США: ACM , стр. 223–228, doi : 10.1145/1055558.1055591 , ISBN. 978-1581138580 , S2CID 6798963
- Уильямс, Р. (2005), «Лучшие нижние границы времени-пространства для SAT и связанных с ним проблем», Конференция IEEE по вычислительной сложности (CCC) , стр. 40–49.
- Уильямс, Р. (2005), «Новый алгоритм оптимального удовлетворения 2-ограничений и его последствия», Theoretical Computer Science , 348 (2–3): 357–365, doi : 10.1016/j.tcs.2005.09.023
- Уильямс, Р. (2008), «Нижние границы пространства-времени для подсчета решений NP по модулю целых чисел», Computational Complexity , 17 (2): 179–219, doi : 10.1007/s00037-008-0248-y , S2CID 8815358
- Уильямс, Р. (2011), «Нижние границы неоднородной схемы ACC», Конференция IEEE по вычислительной сложности (CCC) (PDF) , стр. 115–125, CiteSeerX 10.1.1.225.8935 , doi : 10.1109/CCC.2011.36 , ISBN 978-1-4577-0179-5 , S2CID 7020039
Ссылки
[ редактировать ]- ^ Биографические данные (PDF) , получено 2 декабря 2017 г.
- ^ Райан Уильямс в проекте «Математическая генеалогия»
- ^ «Райан Уильямс | Теория вычислений MIT CSAIL» . toc.csail.mit.edu . Проверено 18 декабря 2021 г.
- ^ Материалы 20-й ежегодной конференции IEEE по сложности вычислений (CCC'05) Сан-Хосе, Калифорния, 11–15 июня, ISBN 0-7695-2364-1 и Двадцать вторая ежегодная конференция IEEE по сложности вычислений (CCC'07) Сан-Диего, Калифорния, 13 июня – 16 марта, ISBN 0-7695-2780-9 .
- ^ «Лучшая студенческая работа по ICALP» . Европейская ассоциация теоретической информатики (EATCS).
- ^ Программа CCC2011 на http://computationalcomplexity.org/.
- ^ Ааронсон, Скотт (8 ноября 2010 г.), «Состояние нижних границ схемы теперь немного менее унизительное» , MIT Technology Review .
- ^ Мейерсон и Уильямс (2004) .
Внешние ссылки
[ редактировать ]- Домашняя страница Райана Уильяма в Массачусетском технологическом институте
- Публикации Райана Уильямса, индексируемые Google Scholar
- Райан Уильямс на DBLP библиографическом сервере
