Ryan O'Donnell (informático)
Científico informático canadiense
Ryan O'Donnell
Alma máter
Conocido porAnálisis de funciones booleanas [pub 1]
Carrera científica
CamposAnálisis de funciones booleanas , Teoría de la complejidad , Teoría del aprendizaje computacional , Dificultad de aproximación , Computación cuántica
TesisAplicaciones computacionales de la sensibilidad al ruido  (2003)
Asesor de doctoradoMadhu Sudán
Sitio webhttps://www.cs.cmu.edu/~odonnell/

Ryan O'Donnell es un científico informático teórico canadiense y profesor de la Universidad Carnegie Mellon . Es conocido por su trabajo sobre el análisis de funciones booleanas y por ser autor del libro de texto sobre este tema. [pub 1] También es conocido por su trabajo sobre la teoría del aprendizaje computacional , la dificultad de aproximación , las pruebas de propiedades , la computación cuántica y la información cuántica .

O'Donnell completó su licenciatura en Matemáticas y Ciencias de la Computación en la Universidad de Toronto . [1] Luego completó su doctorado en el Instituto Tecnológico de Massachusetts (MIT) en 2003, asesorado por Madhu Sudan . [2]

Investigación

O'Donnell demostró que el algoritmo de aproximación de Goemans-Williamson para MAX-CUT es óptimo, suponiendo la conjetura de los juegos únicos . La prueba se desprende de dos artículos, uno en 2004 con Subhash Khot , Guy Kindler y Elchanan Mossel que redujo esta afirmación a la prueba de la conjetura de que la mayoría es más estable en el análisis de funciones booleanas, [pub 2] y uno en 2005 con Elchanan Mossel y Krzysztof Oleszkiewicz que demuestra esta conjetura. [pub 3] Más tarde escribió un influyente libro de texto sobre el análisis de funciones booleanas. [pub 1]

Otras contribuciones notables de O'Donnell incluyen la participación en el primer proyecto Polymath , Polymath1, para desarrollar una prueba combinatoria del teorema de densidad de Hales-Jewett , [3] [pub 4] algoritmos mejorados para problemas en la teoría del aprendizaje computacional , [pub 5] y algoritmos mejorados para la tomografía de estados cuánticos . [pub 6]

Reconocimiento

Recibió el premio CAREER de la National Science Foundation en 2008 y una beca de investigación Sloan en 2009. Dio una conferencia invitada en el Congreso Internacional de Matemáticos en 2014.

Servicio

O'Donnell se desempeñó como editor en jefe de la revista ACM Transactions on Computation Theory de 2019 a 2023 y fue editor de la revista SIAM Journal on Discrete Mathematics de 2012 a 2017. Es miembro del consejo asesor científico del Instituto Simons para la Teoría de la Computación [4] y del consejo científico del Coloquio Electrónico sobre Complejidad Computacional . [5]

O'Donnell opera un canal de YouTube , que tiene más de 10,2 mil suscriptores y más de 680 mil vistas a diciembre de 2023. [6] Allí, imparte conferencias de matemáticas y ciencias de la computación sobre temas como la teoría de la complejidad, la teoría de grafos espectrales y el análisis de funciones booleanas, además de subir conferencias de sus clases en la Universidad Carnegie Mellon. Ha dirigido varias series de cursos, como su serie "CS Theory Toolkit", donde explora áreas matemáticas aplicables al campo de la informática teórica.

Publicaciones seleccionadas

  1. ^ abc O'Donnell, Ryan (2014). Análisis de funciones booleanas . Nueva York: Cambridge University Press. arXiv : 2105.10386 . ISBN. 978-1-107-03832-5.
  2. ^ Khot, Subhash; Kindler, Guy; Mossel, Elchanan; O'Donnell, Ryan (2007). "¿Resultados óptimos de inaproximabilidad para MAX-CUT y otros CSP de 2 variables?". SIAM Journal on Computing . 37 (1): 319–357. doi :10.1137/S0097539705447372. ISSN  0097-5397. S2CID  2090495.
  3. ^ Mossel, Elchanan; O'Donnell, Ryan; Oleszkiewicz, Krzysztof (17 de marzo de 2010). "Estabilidad de ruido de funciones con influencias bajas: invariancia y optimalidad". Anales de Matemáticas . 171 (1): 295–341. arXiv : math/0503503 . doi : 10.4007/annals.2010.171.295 . ISSN  0003-486X.
  4. ^ Polígrafo, DHJ (1 de mayo de 2012). "Una nueva prueba del teorema de densidad de Hales-Jewett". Anales de Matemáticas . 175 (3): 1283–1327. doi : 10.4007/annals.2012.175.3.6 . ISSN  0003-486X.
  5. ^ Klivans, AR; O'Donnell, R.; Servedio, RA (2002). "Intersecciones de aprendizaje y umbrales de semiespacios". 43.° Simposio anual IEEE sobre fundamentos de la informática, 2002. Actas . IEEE. págs. 177–186. doi :10.1109/SFCS.2002.1181894. ISBN. 978-0-7695-1822-0.S2CID1664758  .​
  6. ^ O'Donnell, Ryan; Wright, John (19 de junio de 2017). "Tomografía cuántica eficiente II". Actas del 49.º Simposio anual ACM SIGACT sobre teoría de la computación . ACM. págs. 962–974. doi : 10.1145/3055399.3055454 . ISBN. 978-1-4503-4528-6.

Referencias

  1. ^ "Ryan O'Donnell". www.cs.cmu.edu . Consultado el 18 de diciembre de 2023 .
  2. ^ Ryan O'Donnell en el Proyecto de Genealogía Matemática
  3. ^ "Un enfoque combinatorio de la densidad Hales-Jewett | Blog de Gowers". 2017-03-03. Archivado desde el original el 2017-03-03 . Consultado el 2023-12-13 .
  4. ^ Instituto Simons para la Teoría de la Computación (2023). "Consejo Asesor Científico".
  5. ^ Coloquio Electrónico sobre Complejidad Computacional (2023). "Acerca del coloquio > Comité científico".
  6. ^ "Ryan O'Donnell - YouTube". www.youtube.com . Consultado el 18 de diciembre de 2023 .
  • Sitio web oficial
  • Página de la facultad
  • Canal de YouTube
Retrieved from "https://en.wikipedia.org/w/index.php?title=Ryan_O%27Donnell_(computer_scientist)&oldid=1232383566"