Virginia Vassilevska Williams

Virginia Vassilevska Williams
Virginia Vassilevska Williams
	Vassilevska Williams at Oberwolfach, 2012
Nationality	Bulgarian American
Alma mater	Carnegie Mellon University (PhD, 2008); Caltech (BS, 2003);
Known for	Matrix multiplication; Graph algorithms; Dynamic algorithms; Fine-grained complexity theory;
	Scientific career
Fields	Complexity theory; Algorithms;
Institutions	MIT; Stanford; UC Berkeley; Institute for Advanced Study;
Doctoral advisor	Guy Blelloch

Virginia Vassilevska Williams (née Virginia Panayotova Vassilevska)^[1] is a theoretical computer scientist and mathematician known for her research in computational complexity theory and algorithms. She is currently the Steven and Renee Finn Career Development Associate Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology.^[2] She is notable for her breakthrough results in fast matrix multiplication,^[3] for her work on dynamic algorithms,^[4] and for helping to develop the field of fine-grained complexity.^[5]

Education and career

Williams is originally from Bulgaria, and attended a German-language high school in Sofia.^[6] She graduated from the California Institute of Technology in 2003, and completed her Ph.D. at Carnegie Mellon University in 2008.^[1] Her dissertation, Efficient Algorithms for Path Problems in Weighted Graphs, was supervised by Guy Blelloch.^[7]

After postdoctoral research at the Institute for Advanced Study and University of California, Berkeley, Williams became an assistant professor of computer science at Stanford University in 2013.^[1] She moved to MIT as an associate professor in 2017.^[2]

Research

In 2011, Williams found an algorithm for multiplying two $n\times n$ matrices in time $O(n^{2.373})$ . This improved a previous time bound for matrix multiplication algorithms, the Coppersmith–Winograd algorithm, that had stood as the best known for 24 years. Her initial improvement was independent of Andrew Stothers, who also improved the same bound a year earlier; after learning of Stothers' work, she combined ideas from both methods to improve his bound as well.^[8]^[3] As of 2023, her work also establishes the current best-known algorithm for matrix multiplication with her collaborators, in time $O(n^{2.371552})$ .^[9]^[10]

Recognition

Williams was an NSF Computing Innovation Fellow for 2009–2011,^[1] and won a Sloan Research Fellowship in 2017.^[2] She was an invited speaker at the 2018 International Congress of Mathematicians, speaking in the section on Mathematical Aspects of Computer Science.^[11]

Personal life

Williams is the daughter of applied mathematicians Panayot Vassilevski and Tanya Kostova-Vassilevska.^[12] She is married to Ryan Williams, also a computer science professor at MIT; they have worked together in the field of fine-grained complexity.^[6]

References

^ ^a ^b ^c ^d Curriculum vitae (PDF), retrieved 2018-02-24
^ ^a ^b ^c Three EECS professors receive 2017 Sloan Research Fellowships, Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science, February 22, 2017, archived from the original on 2018-03-22, retrieved 2018-02-25
^ ^a ^b Virginia Vassilevska Williams (2012), "Multiplying Matrices Faster than Coppersmith-Winograd", in Howard J. Karloff and Toniann Pitassi (ed.), Proceedings of the 44th Symposium on Theory of Computing (STOC), ACM, pp. 887–898, CiteSeerX 10.1.1.297.2680, doi:10.1145/2213977.2214056, S2CID 14350287
^ Abboud, Amir; Williams, Virginia Vassilevska (2014), "Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems", 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 434–443, arXiv:1402.0054, doi:10.1109/FOCS.2014.53, ISBN 978-1-4799-6517-5, S2CID 2267837
^ Williams, V. V. (2019), "On Some Fine-Grained Questions in Algorithms and Complexity", Proceedings of the International Congress of Mathematicians (ICM 2018): 3447–3487, doi:10.1142/9789813272880_0188, ISBN 978-981-327-287-3, S2CID 19282287
^ ^a ^b Matheson, Rob (January 7, 2020), "Finding the true potential of algorithms: Using mathematical theory, Virginia Williams coaxes algorithms to run faster or proves they've hit their maximum speed", MIT News, retrieved 2021-12-18
^ Virginia Vassilevska Williams at the Mathematics Genealogy Project
^ Aron, Jacob (December 9, 2011), "Key mathematical tool sees first advance in 24 years", New Scientist
^ Williams, Virginia Vassilevska; Xu, Yinzhan; Xu, Zixuan; Zhou, Renfei (July 16, 2023), "New Bounds for Matrix Multiplication: from Alpha to Omega", arXiv.org, retrieved 2024-03-06
^ "New Breakthrough Brings Matrix Multiplication Closer to Ideal", Quanta Magazine, March 7, 2024, retrieved 2024-03-08
^ "Speakers", ICM 2018, archived from the original on 2017-12-15, retrieved 2018-02-24
^ "Vassilevska, Williams to wed", Engagements, Hartselle Enquirer, August 28, 2008, retrieved 2022-07-10

External links

Home page
Virginia Vassilevska Williams publications indexed by Google Scholar
Virginia Vassilevska Williams at DBLP Bibliography Server

[cv-1] Curriculum vitae (PDF), retrieved 2018-02-24

[sloan-2] Three EECS professors receive 2017 Sloan Research Fellowships, Massachusetts Institute of Technology Department of Electrical Engineering and Computer Science, February 22, 2017, archived from the original on 2018-03-22, retrieved 2018-02-25

[stoc-3] Virginia Vassilevska Williams (2012), "Multiplying Matrices Faster than Coppersmith-Winograd", in Howard J. Karloff and Toniann Pitassi (ed.), Proceedings of the 44th Symposium on Theory of Computing (STOC), ACM, pp. 887–898, CiteSeerX 10.1.1.297.2680, doi:10.1145/2213977.2214056, S2CID 14350287

[dynamiclowerbounds-4] Abboud, Amir; Williams, Virginia Vassilevska (2014), "Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems", 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 434–443, arXiv:1402.0054, doi:10.1109/FOCS.2014.53, ISBN 978-1-4799-6517-5, S2CID 2267837

[finegrained-5] Williams, V. V. (2019), "On Some Fine-Grained Questions in Algorithms and Complexity", Proceedings of the International Congress of Mathematicians (ICM 2018): 3447–3487, doi:10.1142/9789813272880_0188, ISBN 978-981-327-287-3, S2CID 19282287

[true-6] Matheson, Rob (January 7, 2020), "Finding the true potential of algorithms: Using mathematical theory, Virginia Williams coaxes algorithms to run faster or proves they've hit their maximum speed", MIT News, retrieved 2021-12-18

[mgp-7] Virginia Vassilevska Williams at the Mathematics Genealogy Project

[ns-8] Aron, Jacob (December 9, 2011), "Key mathematical tool sees first advance in 24 years", New Scientist

[matrix2023-9] Williams, Virginia Vassilevska; Xu, Yinzhan; Xu, Zixuan; Zhou, Renfei (July 16, 2023), "New Bounds for Matrix Multiplication: from Alpha to Omega", arXiv.org, retrieved 2024-03-06

[quanta2024-10] "New Breakthrough Brings Matrix Multiplication Closer to Ideal", Quanta Magazine, March 7, 2024, retrieved 2024-03-08

[icm-11] "Speakers", ICM 2018, archived from the original on 2017-12-15, retrieved 2018-02-24

[engage-12] "Vassilevska, Williams to wed", Engagements, Hartselle Enquirer, August 28, 2008, retrieved 2022-07-10

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]