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


Some useful links:

MIT EECS Department

MIT CSAIL

MIT Theory of Computation Group

CS Overflow

Computational Social Choice

MIT Accessibility Page

Virginia Vassilevska Williams
Steven and Renee Finn Career Development 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.

Publications      Activities      Students      Teaching      PCs      Bio


Links to my publications:

Sorted according to year of publication

Sorted according to topic:
Activities:

I am a co-organizer of the TCS Women events at STOC, held in 2018, 2019, 2020 and 2021. When STOC is held again in person, do apply for TCS Women travel grant!

In May 2019 I co-organized the Fine-Grained Approximation Algorithms and Complexity Workshop (FG-APX 2019) at Bertinoro.

In October 2018 I co-organized the Rising Stars in EECS workshop at MIT.

Survey on Fine-Grained Complexity: [pdf] that appeared 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]

Students:
I am currently advising these amazing Ph.D. students:
  • Yael Kirkpatrick,
  • Zixuan Xu,
  • Caleb Robelle,
  • Surya Mathialagan (co-advised with Vinod Vaikuntanathan),
  • Ce Jin (co-advised with Ryan Williams),
  • Jenny Kaufmann (co-advised with Madhu Sudan),
  • Shyan Akmal (co-advised with Ryan Williams), and
  • Yinzhan Xu.

Graduated students:
Mina Dalirrooyfard obtained her Ph.D in Spring 2022.
Nicole Wein obtained her Ph.D. from MIT in Summer 2021. She is a DIMACS postdoctoral fellow at Rutgers University.
Rio Lavigne (co-advised with Vinod Vaikuntanathan) obtained her Ph.D. from MIT in Summer 2020. She is now at Apple, where she is in charge of user privacy.
Andrea Lincoln obtained her Ph.D. from MIT in Summer 2020. She is now a postdoctoral fellow at UC Berkeley.
Josh Alman (co-advised with Ryan Williams) obtained his Ph.D. from MIT in 2019. He is now an assistant professor of computer science at Columbia University.
Greg Bodwin received his Ph.D. from MIT in 2018. He is now an assistant professor at the U. Michigan CS Dept.
Amir Abboud graduated from Stanford in 2017 with his Ph.D. He is now a Senior Researcher at the Weizmann Institute of Science. Previously he was part of the theory group at IBM Almaden.
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. He was an assistant professor at the University of San Francisco.

Teaching:
At MIT:
In Spring 2022 I am co-teaching 6.046: Design and Analysis of Algorithms.
In Fall 2021 I taught 6.890: Graph and Matrix Algorithms.
In Spring 2021 I co-taught 6.046: Design and Analysis of Algorithms.
In Fall 2020 I co-taught 6.S078: Fine-grained Algorithms and Complexity.
In Spring 2020 I taught 6.890: Graph and Matrix Algorithms.
In Fall 2019 I co-taught 6.006: Introduction to algorithms.
In Spring 2019 I co-taught 6.006: Introduction to algorithms.
In Spring 2018 I co-taught 6.S078: Fine-grained Algorithms and Complexity.
In Fall 2017 I co-taught 6.046: Design and Analysis of Algorithms.
In Spring 2017 I taught 6.890: Graph and Matrix Algorithms.

At Stanford:
In 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 co-taught CS 266: Parametrized algorithms and complexity.

Program Committee Work:
In the past, I have served on many program committees: FUN 2022, STOC 2021 (chair), SODA 2020, ITCS 2020, 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.


Some info and short bio:
I am originally from Sofia, Bulgaria, where I (mostly) lived until 1999 when I graduated from the amazing German Language High School in Sofia.
As a child, I spent two years in the USA, and I learned English then. I came back to the US for college. In 2003 I graduated from Caltech with B.S. in Mathematics and Eng. and Applied Science (there was no CS degree at the time).
After Caltech, I went to Carnegie Mellon University where in 2008 I got my Ph.D. in Computer Science under Prof. Guy Blelloch.
After CMU I spent a year as a postdoctoral member at the Institute for Advanced Study in Princeton, in Avi Wigderson's group.
Between 2009 and 2011 I was a Computing Innovations Fellow at UC Berkeley, working with Prof. Satish Rao.
After that, I spent two years as a part-time Research Associate at Stanford 2011-2013, and a part-time Assistant Research Engineer at Berkeley.
In 2013 I joined the Computer Science Department at Stanford University as an Assistant Professor.
In early 2017, I moved to MIT as an Associate Professor in EECS. I earned tenure in 2019, and am now a full professor.


CV: [pdf]      Thesis: [pdf]



And here is what Wordle thinks of my publication list: