Richard Ryan Williams , conocido como Ryan Williams (nacido en 1979), es un estadounidense experto en informática que trabaja en la teoría de la complejidad computacional .
Ryan Williams | |
---|---|
Nació | 1979 (41 a 42 años de edad) |
Nacionalidad | americano |
alma mater | Universidad de Cornell Universidad Carnegie Mellon |
Carrera científica | |
Campos | Teoría de la complejidad computacional , algoritmos |
Instituciones | Universidad Carnegie Mellon Centro de Investigación IBM Almaden Universidad de Stanford |
Asesor de doctorado | Manuel Blum |
Educación
Williams recibió su licenciatura en matemáticas y ciencias de la computación de la Universidad de Cornell en 2001 [1] y su doctorado en ciencias de la computación en 2007 de la Universidad Carnegie Mellon bajo la supervisión de Manuel Blum . [2] De 2010 a 2012, fue miembro del Grupo Teórico del Centro de Investigación de IBM Almaden . Desde el otoño de 2011 hasta el otoño de 2016, fue profesor en la Universidad de Stanford. En enero de 2017, se incorporó a la facultad del MIT [1] .
Investigar
Williams ha sido miembro del comité de programa para el Simposio sobre Teoría de la Computación en 2011 y varias otras conferencias. Ganó el premio Ron V. Book al mejor artículo de estudiante en la Conferencia IEEE sobre Complejidad Computacional en 2005 y 2007, [3] y en el premio al mejor artículo de estudiante en el Coloquio Internacional sobre Autómatas, Idiomas y Programación en 2004 de la Asociación Europea para Informática Teórica . [4]
El resultado de Williams de que la clase de complejidad NEXP no está contenida en ACC 0 recibió el premio al mejor artículo en la Conferencia sobre Complejidad Computacional en 2011. [5] El teórico de la complejidad Scott Aaronson ha calificado el resultado como "uno de los más espectaculares de la década". [6]
Williams también es un experto en la complejidad computacional del k- anonimato . [7]
Vida personal
Ryan está casado con Virginia Vassilevska Williams , también científica informática.
Publicaciones Seleccionadas
- Meyerson, Adam; Williams, Ryan (2004), "Sobre la complejidad del k- anonimato óptimo ", Actas del vigésimo tercer simposio ACM SIGMOD-SIGACT-SIGART sobre principios de sistemas de bases de datos (PODS '04) , Nueva York, NY, EE. UU.: ACM , págs. 223–228, doi : 10.1145 / 1055558.1055591 , ISBN 978-1581138580
- Williams, R. (2005), "Mejores límites de tiempo-espacio inferior para SAT y problemas relacionados", Conferencia IEEE sobre complejidad computacional (CCC) , págs. 40–49
- Williams, R. (2005), "A New Algorithm for Optimal 2-Constraint Satisfaction and Its Implications", Theoretical Computer Science , 348 (2–3): 357–365, doi : 10.1016 / j.tcs.2005.09.023
- Williams, R. (2008), "Límites inferiores de tiempo-espacio para contar números enteros de módulo de soluciones NP", Complejidad computacional , 17 (2): 179–219, doi : 10.1007 / s00037-008-0248-y
- Williams, R. (2011), "Non-Uniform ACC Circuit Lower Bounds", IEEE Conference on Computational Complexity (CCC) (PDF) , págs. 115-125, CiteSeerX 10.1.1.225.8935 , doi : 10.1109 / CCC.2011.36 , ISBN 978-1-4577-0179-5
Referencias
- ^ Curriculum vitae (PDF) , consultado el 2 de diciembre de 2017
- ^ Ryan Williams en el Proyecto de genealogía matemática
- ^ Actas de la 20a Conferencia Anual de IEEE sobre Complejidad Computacional (CCC'05) San José, CA 11 de junio-15 de junio ISBN 0-7695-2364-1 y Vigésima Segunda Conferencia Anual IEEE sobre Complejidad Computacional (CCC'07) San Diego, California, 13 de junio al 16 de marzo, ISBN 0-7695-2780-9 .
- ^ "Mejor trabajo de estudiante de ICALP" . Asociación Europea de Ciencias de la Computación Teórica (EATCS).
- ^ Programa para CCC2011 en http://computationalcomplexity.org/
- ^ Aaronson, Scott (8 de noviembre de 2010), "El estado de los límites inferiores del circuito ahora es un poco menos humillante" , MIT Technology Review.
- ^ Meyerson y Williams (2004) .
enlaces externos
- Página de inicio de Ryan William en el MIT
- Publicaciones de Ryan Williams indexadas por Google Scholar