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 explores the relationships between these classifications. A computational problem ...

and

algorithms In mathematics and computer science, an algorithm () is a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for per ...

. 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 university, private research university in Cambridge, Massachusetts, United States. Established in 1861, MIT has played a significant role in the development of many areas of moder ...

. 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, officially the Republic of Bulgaria, is a country in Southeast Europe. It is situated on the eastern portion of the Balkans directly south of the Danube river and west of the Black Sea. Bulgaria is bordered by Greece and Turkey t ...

, and attended a German-language high school in

Sofia Sofia is the Capital city, capital and List of cities and towns in Bulgaria, largest city of Bulgaria. It is situated in the Sofia Valley at the foot of the Vitosha mountain, in the western part of the country. The city is built west of the Is ...

. She graduated from the

California Institute of Technology The California Institute of Technology (branded as Caltech) is a private research university in Pasadena, California, United States. The university is responsible for many modern scientific advancements and is among a small group of institutes ...

in 2003, and completed her Ph.D. at

Carnegie Mellon University Carnegie Mellon University (CMU) is a private research university in Pittsburgh, Pennsylvania, United States. The institution was established in 1900 by Andrew Carnegie as the Carnegie Technical Schools. In 1912, it became the Carnegie Institu ...

in 2008. Her dissertation, ''Efficient Algorithms for Path Problems in Weighted Graphs'', was supervised by Guy Blelloch. After postdoctoral research at the

Institute for Advanced Study The Institute for Advanced Study (IAS) is an independent center for theoretical research and intellectual inquiry located in Princeton, New Jersey. It has served as the academic home of internationally preeminent scholars, including Albert Ein ...

and

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California), is a Public university, public Land-grant university, land-grant research university in Berkeley, California, United States. Founded in 1868 and named after t ...

, Williams became an assistant professor of computer science at

Stanford University Leland Stanford Junior University, commonly referred to as Stanford University, is a Private university, private research university in Stanford, California, United States. It was founded in 1885 by railroad magnate Leland Stanford (the eighth ...

in 2013. She moved to MIT as an associate professor in 2017.

Research

In 2011, Williams found an algorithm for multiplying two

n\times n

matrices in time

O(n^)

. This improved a previous time bound for

matrix multiplication algorithm Because matrix multiplication is such a central operation in many numerical algorithms, much work has been invested in making matrix multiplication algorithms efficient. Applications of matrix multiplication in computational problems are found in m ...

s, 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 2023, her work also establishes the current best-known algorithm for matrix multiplication with her collaborators, in time

O(n^)

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 IMU Abacus Medal (known before ...

, 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 21st-century Bulgarian mathematicians Bulgarian women mathematicians American women computer scientists 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 American women mathematicians