stringtranslate.com

Virginia Vassilevska Williams

Virginia Vassilevska Williams (de soltera Virginia Panayotova Vassilevska) [1] es una científica informática teórica y matemática conocida por su investigación en teoría de la complejidad computacional y algoritmos . Actualmente es profesora asociada de desarrollo profesional Steven y Renee Finn de ingeniería eléctrica y ciencias de la computación en el Instituto Tecnológico de Massachusetts . [2] Es conocida por sus resultados innovadores en la multiplicación rápida de matrices , [3] por su trabajo en algoritmos dinámicos , [4] y por ayudar a desarrollar el campo de la complejidad de grano fino . [5]

Educación y carrera

Williams es originaria de Bulgaria y asistió a una escuela secundaria de lengua alemana en Sofía . [6] Se graduó del Instituto de Tecnología de California en 2003 y completó su doctorado en la Universidad Carnegie Mellon en 2008. [1] Su disertación, Algoritmos eficientes para problemas de trayectorias en gráficos ponderados , fue supervisada por Guy Blelloch . [7]

Después de una investigación postdoctoral en el Instituto de Estudios Avanzados y la Universidad de California, Berkeley , Williams se convirtió en profesora adjunta de informática en la Universidad de Stanford en 2013. [1] Se trasladó al MIT como profesora asociada en 2017. [2]

Investigación

En 2011, Williams encontró un algoritmo para multiplicar dos matrices en tiempo . Esto mejoró un límite temporal anterior para algoritmos de multiplicación de matrices , el algoritmo Coppersmith-Winograd , que había sido el más conocido durante 24 años. Su mejora inicial fue independiente de Andrew Stothers, quien también mejoró el mismo límite un año antes; después de conocer el trabajo de Stothers, combinó ideas de ambos métodos para mejorar también su límite. [8] [3] A partir de 2023, su trabajo también establece el algoritmo más conocido actual para la multiplicación de matrices con sus colaboradores, en tiempo . [9] [10]

Reconocimiento

Williams fue becaria de innovación informática de la NSF entre 2009 y 2011, [1] y ganó una beca de investigación Sloan en 2017. [2] Fue oradora invitada en el Congreso Internacional de Matemáticos de 2018 , hablando en la sección sobre Aspectos matemáticos de la informática. [11]

Vida personal

Williams es hija de los matemáticos aplicados Panayot Vassilevski y Tanya Kostova-Vassilevska. [12] Está casada con Ryan Williams , también profesor de informática en el MIT; han trabajado juntos en el campo de la complejidad de grano fino . [6]

Referencias

  1. ^ abcd Curriculum vitae (PDF) , consultado el 24 de febrero de 2018
  2. ^ abc Tres profesores de EECS reciben becas de investigación Sloan 2017, Departamento de Ingeniería Eléctrica y Ciencias de la Computación del Instituto Tecnológico de Massachusetts, 22 de febrero de 2017, archivado desde el original el 22 de marzo de 2018 , consultado el 25 de febrero de 2018
  3. ^ de Virginia Vassilevska Williams (2012), "Multiplicar matrices más rápido que Coppersmith-Winograd", en Howard J. Karloff y Toniann Pitassi (ed.), Actas del 44.º Simposio sobre teoría de la computación (STOC) , ACM, págs. 887-898, CiteSeerX 10.1.1.297.2680 , doi :10.1145/2213977.2214056, S2CID  14350287 
  4. ^ Abboud, Amir; Williams, Virginia Vassilevska (2014), "Las conjeturas populares implican límites inferiores fuertes para problemas dinámicos", 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, págs. 434–443, arXiv : 1402.0054 , doi :10.1109/FOCS.2014.53, ISBN 978-1-4799-6517-5, Número de identificación del sujeto  2267837
  5. ^ Williams, VV (2019), "Sobre algunas cuestiones de grano fino en algoritmos y complejidad", Actas del Congreso Internacional de Matemáticos (ICM 2018) : 3447–3487, doi :10.1142/9789813272880_0188, ISBN 978-981-327-287-3, Número de identificación del sujeto  19282287
  6. ^ ab Matheson, Rob (7 de enero de 2020), "Encontrar el verdadero potencial de los algoritmos: utilizando la teoría matemática, Virginia Williams convence a los algoritmos de que se ejecuten más rápido o demuestra que han alcanzado su velocidad máxima", MIT News , consultado el 18 de diciembre de 2021
  7. ^ Virginia Vassilevska Williams en el Proyecto de Genealogía Matemática
  8. ^ Aron, Jacob (9 de diciembre de 2011), "Una herramienta matemática clave logra el primer avance en 24 años", New Scientist
  9. ^ Williams, Virginia Vassilevska; Xu, Yinzhan; Xu, Zixuan; Zhou, Renfei (16 de julio de 2023), "Nuevos límites para la multiplicación de matrices: de alfa a omega", arXiv.org , consultado el 6 de marzo de 2024
  10. ^ "Un nuevo avance acerca la multiplicación de matrices al ideal", Quanta Magazine , 7 de marzo de 2024 , consultado el 8 de marzo de 2024
  11. ^ "Oradores", ICM 2018 , archivado desde el original el 15 de diciembre de 2017 , consultado el 24 de febrero de 2018
  12. ^ "Vassilevska y Williams se casarán", Compromisos, Hartselle Enquirer , 28 de agosto de 2008 , consultado el 10 de julio de 2022

Enlaces externos