Contact information:
Email: virgi at mit dot edu
Phone: 617-715-5833
Office: 32-G640




Some useful links:

MIT EECS Department

MIT Theory of Computation Group

CS Overflow

Computational Social Choice

Virginia Vassilevska Williams
Steven and Renee Finn Career Development Associate Professor

My research applies combinatorial and graph theoretic tools to various computational domains. My recent work has focused on the following domains:
  • designing algorithms for shortest paths, pattern detection and other computational problems in graphs and matrices,
  • reducing fundamental computational problems to one another in a fine-grained way, sometimes showing equivalences,
  • studying how much graph distance information can be compressed, and
  • computational issues in social choice: when and how can one efficiently manipulate elections, tournaments and competitions, how to measure the quality of a voting rule, etc.

Links to my publications:

Sorted according to year of publication

Sorted according to topic:
Activities:

New Survey on Fine-Grained Complexity: [pdf] to appear in the proceedings of the ICM 2018.

In November 2016, I co-organized a Dagstuhl workshop on "Hardness and Structure in P": [workshop website]. Here is the Open Problems pdf.

In June 2016, I co-organized a joint STOC-SOCG workshop on "Spanners: Graphs and Geometry": [workshop website]

In the Fall 2015, I co-organized a program at the Simons Institute on Fine-Grained Complexity and Algorithms.

At STOC'15 in Portland I co-organized a tutorial on conditional lower bounds for problems within polynomial time: Hardness for Easy Problems

Here is a survey I wrote back in September 2015 on Fine-grained complexity: [pdf]

My not so recent results on matrix multiplication: [full version pdf], [Maple files]
(I showed that omega is less than 2.373.)
Here is my 2012 SIGACT News article on the topic.

Students:
I am currently advising these amazing Ph.D. students:
Josh Alman (co-advised with Ryan Williams), Mina Dalirrooyfard, Rio Lavigne (co-advised with Vinod Vaikuntanathan), Andrea Lincoln, Dan Stubbs, and Nicole Wein.

My student Greg Bodwin received his Ph.D. from MIT in 2018. He has joined the Theory Group and Georgia Tech as a postdoctoral fellow.
My student Amir Abboud graduated from Stanford in 2017 with his Ph.D. He is now at the theory group at IBM Almaden.
My student Haden Lee graduated with a Ph.D. from Stanford in 2016 (co-advised by Ashish Goel and Yoav Shoham). He is now a research scientist at Moloco.

Teaching:
At MIT:
In the Spring 2018 I cotaught 6.S078: Fine-grained Algorithms and Complexity.
In the Fall 2017 I taught 6.046: Introduction to Algorithms.
In the Spring 2017 I taught 6.890: Graph and Matrix Algorithms.

At Stanford:
In the Fall 2016 I taught CS 267, Graph Algorithms.
In the Spring 2016 quarter I taught CS 161, Introduction to Algorithms.
In the Winter 2016 quarter I taught CS 267, Graph Algorithms..
In the Fall 2015 quarter I taught CS 367, Algebraic Graph Algorithms.
In the Spring 2015 quarter I taught CS 161, Introduction to Algorithms.
In the Winter 2015 quarter I taught CS 267, Graph Algorithms..
In the Spring 2014 quarter I taught CS 367, Algebraic Graph Algorithms.
During the Winter 2014 quarter I taught CS 267, Graph Algorithms.
During the Spring 2013 quarter I cotaught CS 266: Parametrized algorithms and complexity.

Program Committee Work:
In the past, I have served on the following program committees: ICALP 2018, SOSA 2018, STACS 2018, IPEC 2017, AAMAS 2017, WADS 2017, ITCS 2017, SODA 2017, FUN 2016, HALG 2016, IJCAI 2016, ESA 2015, COMSOC 2014, STOC 2013, ICALP 2013, IJCAI 2013, FOCS 2013, COMSOC 2012, AAMAS 2012, AAAI 2012, SWAT 2012, and SODA 2013.


Short bio:
B.S. in Mathematics and Eng. and Applied Science (CS), Caltech, 2003
Ph.D. in Computer Science, Carnegie Mellon, 2008, under Prof. Guy Blelloch
Member of the IAS in Avi Wigderson's group, 2008-2009
Computing Innovations Fellow, Berkeley, working with Prof. Satish Rao, 2009-2011
Part-time Research Associate at Stanford 2011-2013
Part-time Assistant Research Engineer at Berkeley, 2011-2013
Assistant Professor in Computer Science, Stanford University, 2013-2016


CV: [pdf]      Thesis: [pdf]



And here is what Wordle thinks of my publication list: