Publications on Other Topics
  • Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More, Mina Dalirrooyfard, Andrea Lincoln, Barna Saha and Virginia Vassilevska Williams.

    		• SODA 2025


    		[TO COME]

  • Faster Algorithms for Text-to-Pattern Hamming Distances, Timothy Chan, Ce Jin, Virginia Vassilevska Williams and Yinzhan Xu.

    		• FOCS 2023


    		[arXiv]

  • Improved Approximation for Longest Common Subsequence over Small Alphabets, Shyan Akmal and V. Vassilevska Williams.

    		• ICALP 2021


    		[TO COME]

  • Fine-Grained Hardness for Edit Distance to a Fixed Sequence, Amir Abboud and V. Vassilevska Williams.

    		• ICALP 2021


    		[TO COME]

  • Public-Key Cryptography in the Fine-Grained Setting, Rio LaVigne, Andrea Lincoln and V. Vassilevska Williams.

    		• CRYPTO 2019


    		[to come]

  • Deterministic Time-Space Tradeoffs for k-SUM, Andrea Lincoln, V. Vassilevska Williams, Josh R. Wang and Ryan Williams.

    		• ICALP 2016


    		[pdf]

  • Simulating Branching Programs with Edit Distance and Friends or: A Polylog Shaved is a Lower Bound Made, Amir Abboud, Thomas D. Hansen, V. Vassilevska Williams and Ryan Williams.

    		• STOC 2016


    		[pdf]

  • Tight Hardness Results for LCS and other Sequence Similarity Measures, Amir Abboud, Arturs Backurs, and V. Vassilevska Williams.

    		• FOCS 2015


    		[pdf]

  • Consequences of faster sequence alignment, Amir Abboud, V. Vassilevska Williams, Oren Weimann.

    		• ICALP 2014


    		[pdf]

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

    		• Tech Report [pdf]

  • 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]