Virginia Vassilevska Williams (née Virginia Panayotova Vassilevska) is a theoretical computer scientist and mathematician known for her research in
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
and
algorithms
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
. She is currently the Steven and Renee Finn Career Development Associate Professor of Electrical Engineering and Computer Science at the
Massachusetts Institute of Technology
The Massachusetts Institute of Technology (MIT) is a private land-grant research university in Cambridge, Massachusetts. Established in 1861, MIT has played a key role in the development of modern technology and science, and is one of th ...
. She is notable for her breakthrough results in
fast matrix multiplication, for her work on
dynamic algorithms, and for helping to develop the field of
fine-grained complexity.
Education and career
Williams is originally from
Bulgaria
Bulgaria (; bg, България, Bǎlgariya), officially the Republic of Bulgaria,, ) is a country in Southeast Europe. It is situated on the eastern flank of the Balkans, and is bordered by Romania to the north, Serbia and North Macedo ...
, and attended a German-language high school in
Sofia
Sofia ( ; bg, София, Sofiya, ) is the capital and largest city of Bulgaria. It is situated in the Sofia Valley at the foot of the Vitosha mountain in the western parts of the country. The city is built west of the Iskar river, and h ...
. She graduated from the
California Institute of Technology
The California Institute of Technology (branded as Caltech or CIT)The university itself only spells its short form as "Caltech"; the institution considers other spellings such a"Cal Tech" and "CalTech" incorrect. The institute is also occasional ...
in 2003, and completed her Ph.D. at
Carnegie Mellon University
Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania. One of its predecessors was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools; it became the Carnegie Institute of Technology ...
in 2008. Her dissertation, ''Efficient Algorithms for Path Problems in Weighted Graphs'', was supervised by
Guy Blelloch
Guy Edward Blelloch is a professor of computer science at Carnegie Mellon University. He is known for his work in parallel programming and parallel algorithms. He teaches the 15-853: Algorithms in the Real World course, the 15-492: Parallel Algor ...
.
After postdoctoral research at the
Institute for Advanced Study
The Institute for Advanced Study (IAS), located in Princeton, New Jersey, in the United States, is an independent center for theoretical research and intellectual inquiry. It has served as the academic home of internationally preeminent schola ...
and
University of California, Berkeley
The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California) is a public land-grant research university in Berkeley, California. Established in 1868 as the University of California, it is the state's first land-grant un ...
, Williams became an assistant professor of computer science at
Stanford University
Stanford University, officially Leland Stanford Junior University, is a private research university in Stanford, California. The campus occupies , among the largest in the United States, and enrolls over 17,000 students. Stanford is conside ...
in 2013. She moved to MIT as an associate professor in 2017.
Research
In 2011, Williams found an algorithm for multiplying two
matrices in time
. 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. As of 2020, her work also establishes the current best-known algorithm for matrix multiplication with Josh Alman, in time
.
Recognition
Williams was an NSF Computing Innovation Fellow for 2009–2011, and won a Sloan Research Fellowship in 2017. She was an invited speaker at the 2018
International Congress of Mathematicians
The International Congress of Mathematicians (ICM) is the largest conference for the topic of mathematics. It meets once every four years, hosted by the International Mathematical Union (IMU).
The Fields Medals, the Nevanlinna Prize (to be rena ...
, speaking in the section on Mathematical Aspects of Computer Science.
Personal life
Williams is the daughter of applied mathematicians Panayot Vassilevski and Tanya Kostova-Vassilevska. She is married to
Ryan Williams, also a computer science professor at MIT; they have worked together in the field of
fine-grained complexity.
References
External links
Home page*
*
{{DEFAULTSORT:Williams, Virginia Vassilevska
Year of birth missing (living people)
Living people
American computer scientists
21st-century American mathematicians
Bulgarian mathematicians
Bulgarian women mathematicians
American women computer scientists
American women mathematicians
Theoretical computer scientists
California Institute of Technology alumni
Carnegie Mellon University alumni
Stanford University faculty
MIT School of Engineering faculty
American people of Bulgarian descent
21st-century women mathematicians
21st-century American women