Райан О'Доннелл (ученый-компьютерщик)
 | В этой статье есть несколько проблем. Пожалуйста, помогите улучшить его или обсудите эти проблемы на странице обсуждения . ( Узнайте, как и когда удалять эти шаблонные сообщения )
|
Райан О'Доннелл | |
|---|---|
| Альма-матер | |
| Известный | Анализ булевых функций [ паб 1 ] |
| Научная карьера | |
| Поля | Анализ булевых функций , Теория сложности , Теория вычислительного обучения , Твердость аппроксимации , Квантовые вычисления |
| Диссертация | Вычислительные применения чувствительности к шуму (2003) |
| Докторантура | Мадху Судан |
| Веб-сайт | https://www.cs.cmu.edu/~odonnell/ |
Райан О'Доннелл — канадский ученый-теоретик в области информатики и профессор Университета Карнеги-Меллон . Он известен своими работами по анализу булевых функций и автором учебника по этому предмету. [ паб 1 ] Он также известен своими работами по теории вычислительного обучения , сложности аппроксимации , проверке свойств , квантовым вычислениям и квантовой информации .
О'Доннелл получил степень бакалавра наук. по математике и информатике в Университете Торонто . [ 1 ] Затем он защитил докторскую диссертацию. в Массачусетском технологическом институте (MIT) в 2003 году по рекомендации Мадху Судана . [ 2 ]
Исследовать
[ редактировать ]О'Доннелл доказал, что алгоритм аппроксимации Гоеманса-Вильямсона для MAX-CUT является оптимальным, если принять гипотезу об уникальных играх . Доказательство следует из двух статей, одна из которых написана в 2004 году Субхашем Хотом , Гаем Киндлером и Эльчананом Мосселем, которые свели это утверждение к доказательству гипотезы «большинство стабильнее» при анализе булевых функций: [ паб 2 ] и один в 2005 году с Эльхананом Мосселем и Кшиштофом Олешкевичем, который доказывает эту гипотезу. [ паб 3 ] Позже он написал влиятельный учебник по анализу булевых функций. [ паб 1 ]
Среди других заметных вкладов О'Доннелла - участие в первом проекте Polymath , Polymath1, по разработке комбинаторного доказательства теоремы Хейлса-Джеветта о плотности . [ 3 ] [ паб 4 ] улучшенные алгоритмы для решения задач вычислительной теории обучения , [ паб 5 ] и улучшенные алгоритмы томографии квантовых состояний . [ паб 6 ]
Признание
[ редактировать ]Он получил премию Национального научного фонда CAREER Award в 2008 году и исследовательскую стипендию Слоана в 2009 году. Он прочитал приглашенную лекцию на Международном конгрессе математиков в 2014 году.
Услуга
[ редактировать ]О'Доннелл работал главным редактором журнала ACM Transactions on Computation Theory с 2019 по 2023 год и был редактором журнала SIAM Journal on Discrete Mathematics с 2012 по 2017 год. Он входит в научно-консультативный совет Института Саймонса. по теории вычислений [ 4 ] и в научном совете Электронного коллоквиума по сложности вычислений . [ 5 ]
О'Доннелл управляет каналом на YouTube , у которого по состоянию на декабрь 2023 года более 10,2 тыс. подписчиков и более 680 тыс. просмотров. [ 6 ] Там он читает лекции по математике и информатике по таким темам, как теория сложности, теория спектральных графов и анализ логических функций, а также загружает лекции со своих занятий в Университете Карнеги-Меллона. Он руководил несколькими сериями курсов, такими как серия «Инструментарий по теории CS», в которой он исследует математические области, применимые к области теоретической информатики.
Избранные публикации
[ редактировать ]- ^ Jump up to: а б с О'Доннелл, Райан (2014). Анализ булевых функций . Нью-Йорк: Издательство Кембриджского университета. arXiv : 2105.10386 . ISBN 978-1-107-03832-5 .
- ^ Хот, Субхаш; Киндлер, Гай; Моссель, Эльханан; О'Доннелл, Райан (2007). «Оптимальные результаты неаппроксимируемости для MAX-CUT и других CSP с двумя переменными?» . SIAM Journal по вычислительной технике . 37 (1): 319–357. дои : 10.1137/S0097539705447372 . ISSN 0097-5397 . S2CID 2090495 .
- ^ Моссель, Эльханан; О'Доннелл, Райан; Олешкевич, Кшиштоф (17 марта 2010 г.). «Помехоустойчивость функций с малыми воздействиями: инвариантность и оптимальность» . Анналы математики . 171 (1): 295–341. arXiv : math/0503503 . дои : 10.4007/анналы.2010.171.295 . ISSN 0003-486X .
- ^ Полимат, DHJ (01 мая 2012 г.). «Новое доказательство теоремы Хейлса-Джеветта о плотности» . Анналы математики . 175 (3): 1283–1327. дои : 10.4007/анналы.2012.175.3.6 . ISSN 0003-486X .
- ^ Кливанс, Арканзас; О'Доннелл, Р.; Серведио, РА (2002). «Изучение пересечений и порогов полупространств» . 43-й ежегодный симпозиум IEEE по основам информатики, 2002 г. Материалы . IEEE. стр. 177–186. дои : 10.1109/SFCS.2002.1181894 . ISBN 978-0-7695-1822-0 . S2CID 1664758 .
- ^ О'Доннелл, Райан; Райт, Джон (19 июня 2017 г.). «Эффективная квантовая томография II». Материалы 49-го ежегодного симпозиума ACM SIGACT по теории вычислений . АКМ. стр. 962–974. дои : 10.1145/3055399.3055454 . ISBN 978-1-4503-4528-6 .
Ссылки
[ редактировать ]- ^ «Райан О'Доннелл» . www.cs.cmu.edu . Проверено 18 декабря 2023 г.
- ^ Райан О'Доннелл в проекте «Математическая генеалогия»
- ^ «Комбинаторный подход к плотности Хейлза-Джеветта | Блог Гауэрса» . 03.03.2017. Архивировано из оригинала 3 марта 2017 г. Проверено 13 декабря 2023 г.
- ^ Институт теории вычислений Саймонса (2023 г.). «Научно-консультативный совет» .
- ^ Электронный коллоквиум по сложности вычислений (2023 г.). «О коллоквиуме > Ученый совет» .
- ^ «Райан О'Доннелл — YouTube» . www.youtube.com . Проверено 18 декабря 2023 г.