Virginia Vassilevska Williams
 I am currently a postdoc at the CS division at UC Berkeley. Here is my new webpage.
I was a member of the IAS for the 2008-2009 academic year.
My work is primarily on graph algorithms with an emphasis on problems related to graph shortest paths.

I received my Ph.D. in Computer Science in August, 2008 from Carnegie Mellon University under the guidance of Prof. Guy Blelloch. Before that I received a Bachelor's degree in Mathematics and Engineering and Applied Science from the California Institute of Technology in 2003, and a Master's degree in Computer Science from Carnegie Mellon University in 2007.


Contact information:
email: virgi at ias
office: Simonyi 007
phone: 609-734-8090



My CV: [ps] [pdf]


Publications

Thesis: [pdf]

Under Submission:
  • Fixing a Tournament, V. Vassilevska.

  • Nondecreasing Paths in a Weighted Graph or: How to Optimally Read a Train Schedule, V. Vassilevska, journal version.


Manuscripts:
  • Ordered Subsets with Applications, Guy Blelloch, V. Vassilevska, 2007.

  • Traceable Data Structures, Umut Acar, Guy Blelloch, Srinath Sridhar, V. Vassilevska, 2006.


Published Articles by Year:

2009:
  • All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time,, V. Vassilevska, Ryan Williams, Raphael Yuster.

    		• Theory of Computing [ToC]

  • Finding, Minimizing and Counting Weighted Subgraphs, V. Vassilevska, Ryan Williams.

    		• STOC [ACM] [ps] [pdf]

2008:
  • Efficient Algorithms for Clique Problems, V. Vassilevska.

    		• Information Processing Letters [IPL] [ps] [pdf]
  • Finding Heaviest H-Subgraphs in Real Weighted Graphs, with Applications, V. Vassilevska, Ryan Williams, Raphael Yuster.

    		• ACM Transactions on Algorithms [ACM] [ps] [pdf]
  • A New Combinatorial Approach to Sparse Graph Problems, Guy Blelloch, V. Vassilevska, Ryan Williams.

    		• ICALP [Springer] [ps] [pdf]
  • Uniquely Represented Data Structures for Computational Geometry, Guy Blelloch, Daniel Golovin, V. Vassilevska.

    		• SWAT [Springer] [ps] [pdf]
  • Uniquely Represented Data Structures for Computational Geometry, Guy Blelloch, Daniel Golovin, V. Vassilevska, Carnegie Mellon University Technical Report CMU-CS-08-115.

    		• Tech Report [pdf]
  • Nondecreasing Paths in a Weighted Graph or: How to Optimally Read a Train Schedule,
    V. Vassilevska, invited to SODA Special Issue.

    		• SODA [ACM] [pdf]
2007:
  • All Pairs Bottleneck Paths in General Graphs in Truly Subcubic Time, V. Vassilevska, Ryan Williams, Raphael Yuster.

    		• STOC [ACM] [ps] [pdf]

  • A Two Player Game to Combat WebSpam, Michelle Goodstein, V. Vassilevska, Carnegie Mellon University Technical Report CMU-CS-07-134.

    		• Tech Report [pdf]

2006:
  • Finding the Smallest H-Subgraph in Real Weighted Graphs and Related Problems, V. Vassilevska, Ryan Williams, Raphael Yuster.

    		• ICALP [Springer] [pdf]

  • Finding a Maximum Weight Triangle in Sub-Cubic Time, With Applications, V. Vassilevska, Ryan Williams.

    		• STOC [ACM] [ps] [pdf]

  • Finding Heaviest H-Subgraphs in Real Weighted Graphs, with Applications, V. Vassilevska, Ryan Williams, Raphael Yuster, arXiv Technical Report: http://www.citebase.org/abstract?id=oai:arXiv.org:cs/0609009.

    		• arXiv Tech Report
  • Confronting Hardness Using A Hybrid Approach, V. Vassilevska, Ryan Williams, S. L. Maverick Woo.
    		• SODA [ACM] [pdf]

2005:
  • Explicit Inapproximability Bounds for the Shortest Superstring Problem, V. Vassilevska.
    		• MFCS [Springer] [ps]

  • Confronting Hardness Using a Hybrid Approach, V. Vassilevska, Ryan Williams, Shan Leung Maverick Woo, Carnegie Mellon University Technical Report CMU-CS-05-125.

    		• Tech Report [pdf] [ps]
  • Finding Nonoverlapping Dense Blocks of a Sparse Matrix, Ali Pinar, V. Vassilevska, the special issue of ETNA on Combinatorial Scientific Computing, 2005.
    		• Electronic Transactions on Numerical Analysis [ETNA]
And here is what Wordle thinks of my publication list: