Райан О'Доннелл (специалист по информатике)
Канадский учёный-компьютерщик
Райан О'Доннелл
Альма-матер
ИзвестныйАнализ булевых функций [pub 1]
Научная карьера
ПоляАнализ булевых функций , Теория сложности , Теория вычислительного обучения , Сложность аппроксимации , Квантовые вычисления
ТезисВычислительные приложения чувствительности к шуму  (2003)
научный руководительМадху Судан
Веб-сайтhttps://www.cs.cmu.edu/~odonnell/

Райан О'Доннелл — канадский теоретик-компьютерщик и профессор Университета Карнеги-Меллона . Он известен своей работой по анализу булевых функций и написанием учебника по этой теме. [pub 1] Он также известен своей работой по теории вычислительного обучения , сложности аппроксимации , тестированию свойств , квантовым вычислениям и квантовой информации .

О'Доннелл получил степень бакалавра наук по математике и информатике в Университете Торонто . [1] Затем в 2003 году он получил степень доктора философии в Массачусетском технологическом институте (MIT) под руководством Мадху Судана . [2]

Исследовать

О'Доннелл доказал, что алгоритм приближения Гоеманса–Вильямсона для MAX-CUT является оптимальным, предполагая гипотезу уникальных игр . Доказательство следует из двух статей, одна в 2004 году с Субхашем Хотом , Гаем Киндлером и Элхананом Мосселем, которая свела это утверждение к доказательству гипотезы «большинство является наиболее стабильным» в анализе булевых функций, [pub 2] и одна в 2005 году с Элхананом Мосселем и Кшиштофом Олешкевичем, которая доказывает эту гипотезу. [pub 3] Позже он написал влиятельный учебник по анализу булевых функций. [pub 1]

Другие заметные вклады О'Доннелла включают участие в первом проекте Polymath , Polymath1, для разработки комбинаторного доказательства теоремы плотности Хейлза–Джеветта , [3] [pub 4] улучшенные алгоритмы для задач в теории вычислительного обучения , [pub 5] и улучшенные алгоритмы для томографии квантовых состояний . [pub 6]

Признание

В 2008 году он получил премию Национального научного фонда CAREER Award , а в 2009 году — исследовательскую стипендию Слоуна . В 2014 году он выступил с приглашенной лекцией на Международном конгрессе математиков .

Услуга

О'Доннелл был главным редактором журнала ACM Transactions on Computation Theory с 2019 по 2023 год и редактором журнала SIAM Journal on Discrete Mathematics с 2012 по 2017 год. Он входит в научный консультативный совет Института Саймонса по теории вычислений [4] и в научный совет Электронного коллоквиума по вычислительной сложности [5] .

О'Доннелл управляет каналом YouTube , который имеет 10,2 тыс. подписчиков и 680 тыс. просмотров по состоянию на декабрь 2023 года. [6] Там он читает лекции по математике и информатике на такие темы, как теория сложности, спектральная теория графов и анализ булевых функций, а также загружает лекции со своих занятий в Университете Карнеги-Меллона. Он руководил несколькими сериями курсов, такими как его серия «CS Theory Toolkit», где он исследует математические области, применимые к области теоретической информатики.

Избранные публикации

  1. ^ abc O'Donnell, Ryan (2014). Анализ булевых функций . Нью-Йорк: Cambridge University Press. arXiv : 2105.10386 . ISBN 978-1-107-03832-5.
  2. ^ Хот, Субхаш; Киндлер, Гай; Моссел, Элханан; О'Доннелл, Райан (2007). «Результаты оптимальной неаппроксимируемости для MAX-CUT и других 2-переменных CSP?». SIAM Journal on Computing . 37 (1): 319– 357. doi :10.1137/S0097539705447372. ISSN  0097-5397. S2CID  2090495.
  3. ^ Моссел, Элханан; О'Доннелл, Райан; Олешкевич, Кшиштоф (2010-03-17). «Шумовая устойчивость функций с малыми влияниями: инвариантность и оптимальность». Annals of Mathematics . 171 (1): 295–341 . arXiv : math/0503503 . doi : 10.4007/annals.2010.171.295 . ISSN  0003-486X.
  4. ^ Polymath, DHJ (2012-05-01). "Новое доказательство теоремы плотности Хейлза-Джеветта". Annals of Mathematics . 175 (3): 1283– 1327. doi : 10.4007/annals.2012.175.3.6 . ISSN  0003-486X.
  5. ^ Кливанс, AR; О'Доннелл, R.; Серведио, RA (2002). «Изучение пересечений и порогов полупространств». 43-й ежегодный симпозиум IEEE по основам компьютерной науки, 2002. Труды . IEEE. стр.  177–186 . doi :10.1109/SFCS.2002.1181894. ISBN 978-0-7695-1822-0. S2CID  1664758.
  6. ^ О'Доннелл, Райан; Райт, Джон (2017-06-19). "Эффективная квантовая томография II". Труды 49-го ежегодного симпозиума ACM SIGACT по теории вычислений . ACM. стр.  962–974 . doi : 10.1145/3055399.3055454 . ISBN 978-1-4503-4528-6.

Ссылки

  1. ^ "Райан О'Доннелл". www.cs.cmu.edu . Получено 2023-12-18 .
  2. ^ Райан О'Доннелл в проекте «Генеалогия математики»
  3. ^ "Комбинаторный подход к плотности Hales-Jewett | Gowers's Weblog". 2017-03-03. Архивировано из оригинала 2017-03-03 . Получено 2023-12-13 .
  4. ^ Институт теории вычислений Саймонса (2023). «Научно-консультативный совет».
  5. ^ Электронный коллоквиум по вычислительной сложности (2023). "О коллоквиуме > Ученый совет".
  6. ^ "Райан О'Доннелл - YouTube". www.youtube.com . Получено 2023-12-18 .
  • Официальный сайт
  • Страница факультета
  • Канал на YouTube
Retrieved from "https://en.wikipedia.org/w/index.php?title=Ryan_O%27Donnell_(computer_scientist)&oldid=1232383566"