Райан О'Доннелл — канадский ученый-теоретик в области информатики и профессор Университета Карнеги-Меллон . Он известен своими работами по анализу булевых функций и автором учебника по этому предмету. [pub 1] Он также известен своими работами по теории вычислительного обучения , твердости аппроксимации , проверке свойств , квантовым вычислениям и квантовой информации .
О'Доннелл получил степень бакалавра наук. по математике и информатике в Университете Торонто . [1] Затем он защитил докторскую диссертацию. в Массачусетском технологическом институте (MIT) в 2003 году по рекомендации Мадху Судана . [2]
О'Доннелл доказал, что алгоритм аппроксимации Гоеманса-Вильямсона для MAX-CUT является оптимальным, если принять гипотезу об уникальных играх . Доказательство следует из двух статей: одна в 2004 году с Субхашем Хотом , Гаем Киндлером и Эльхананом Мосселем , которая свела это утверждение к доказательству гипотезы «большинство стабильнее» при анализе булевых функций, [pub 2] и одна в 2005 году с Эльхананом Мосселем и Кшиштофом. Олешкевича, что доказывает эту гипотезу. [pub 3] Позже он написал влиятельный учебник по анализу булевых функций. [паб 1]
Другие заметные вклады О'Доннелла включают участие в первом проекте Polymath , Polymath1, для разработки комбинаторного доказательства теоремы Хейлса-Джеветта о плотности , [3] [pub 4] улучшенных алгоритмов для задач вычислительной теории обучения , [pub 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», в которой он исследует математические области, применимые к области теоретической информатики.