Virginia Vassilevska Williams

Virginia Vassilevska Williams
Virginia Vassilevska Williams
	Vassilevska Williams på Oberwolfach , 2012
Nationalitet	Bulgarisk amerikan
Alma mater	Carnegie Mellon University (PhD, 2008) ; Caltech (BS, 2003) ;
Känd för	Matrismultiplikation; Grafalgoritmer; Dynamiska algoritmer; Finkornig komplexitetsteori;
	Vetenskaplig karriär
Fält	Komplexitetsteori; Algoritmer;
institutioner	MIT; Stanford; UC Berkeley; Institutet för avancerade studier;
Doktorand rådgivare	Guy Blloch

Virginia Vassilevska Williams (född Virginia Panayotova Vassilevska) är en teoretisk datavetare och matematiker känd för sin forskning inom beräkningskomplexitetsteori och algoritmer . Hon är för närvarande Steven och Renee Finn karriärutvecklingsdocent i elektroteknik och datavetenskap vid Massachusetts Institute of Technology . Hon är känd för sina genombrottsresultat inom snabb matrismultiplikation , för sitt arbete med dynamiska algoritmer och för att ha hjälpt till att utveckla området för finkornig komplexitet .

Utbildning och karriär

Williams kommer ursprungligen från Bulgarien och gick på en tyskspråkig gymnasieskola i Sofia . Hon tog examen från California Institute of Technology 2003 och avslutade sin doktorsexamen. vid Carnegie Mellon University 2008. Hennes avhandling, Efficient Algorithms for Path Problems in Weighted Graphs , handledes av Guy Blelloch .

Efter postdoktoral forskning vid Institute for Advanced Study och University of California, Berkeley , blev Williams biträdande professor i datavetenskap vid Stanford University 2013. Hon flyttade till MIT som docent 2017.

Forskning

År 2011 hittade Williams en algoritm för att multiplicera två $n\times n$ matriser i tiden $) {\displaystyle O(n^{2.373})$ . Detta förbättrade en tidigare tid bunden för matrismultiplikationsalgoritmer, Coppersmith –Winograd-algoritmen, som hade stått som den mest kända i 24 år. Hennes första förbättring var oberoende av Andrew Stothers, som också förbättrade samma gräns ett år tidigare; efter att ha lärt sig om Stothers arbete, kombinerade hon idéer från båda metoderna för att förbättra hans gräns också. Från och med 2020 etablerar hennes arbete också den nuvarande mest kända algoritmen för matrismultiplikation med Josh Alman, i tiden $O(n^{2.3728596})$ .

Erkännande

Williams var NSF Computing Innovation Fellow 2009–2011 och vann ett Sloan Research Fellowship 2017. Hon var en inbjuden talare vid 2018 International Congress of Mathematicians, och talade i avsnittet om matematiska aspekter av datavetenskap.

Privatliv

Williams är dotter till tillämpade matematiker Panayot Vassilevski och Tanya Kostova-Vassilevska. Hon är gift med Ryan Williams , också en professor i datavetenskap vid MIT; de har arbetat tillsammans inom området finkornig komplexitet .

externa länkar

Hemsida
Virginia Vassilevska Williams publikationer indexerade av Google Scholar
Virginia Vassilevska Williams på DBLP Bibliography Server