49 citations · 193 across the 39 of their papers we have counts for
6 papers · 1 filter
Near-Tight Algorithms for the Chamberlin-Courant and Thiele Voting Rules
Krzysztof Sornat, Virginia Vassilevska Williams, Yinzhan Xu
We present an almost optimal algorithm for the classic Chamberlin-Courant multiwinner voting rule (CC) on single-peaked preference profiles. Given voters and candidates, it…
Algorithms and Lower Bounds for Replacement Paths under Multiple Edge Failures
Virginia Vassilevska Williams, Eyob Woldeghebriel, Yinzhan Xu
This paper considers a natural fault-tolerant shortest paths problem: for some constant integer , given a directed weighted graph with no negative cycles and two fixed vertices…
Induced Cycles and Paths Are Harder Than You Think
Mina Dalirrooyfard, Virginia Vassilevska Williams
The goal of the paper is to give fine-grained hardness results for the Subgraph Isomorphism (SI) problem for fixed size induced patterns , based on the -Clique hypothesis tha…
Listing, Verifying and Counting Lowest Common Ancestors in DAGs: Algorithms and Fine-Grained Lower Bounds
Surya Mathialagan, Virginia Vassilevska Williams, Yinzhan Xu
The AP-LCA problem asks, given an -node directed acyclic graph (DAG), to compute for every pair of vertices and in the DAG a lowest common ancestor (LCA) of and …
Hardness for Triangle Problems under Even More Believable Hypotheses: Reductions from Real APSP, Real 3SUM, and OV
Timothy M. Chan, Virginia Vassilevska Williams, Yinzhan Xu
The SUM hypothesis, the APSP hypothesis and SETH are the three main hypotheses in fine-grained complexity. So far, within the area, the first two hypotheses have mainly been abo…
Approximation Algorithms and Hardness for -Pairs Shortest Paths and All-Nodes Shortest Cycles
Mina Dalirrooyfard, Ce Jin, Virginia Vassilevska Williams +1
We study the approximability of two related problems on graphs with nodes and edges: -Pairs Shortest Paths (-PSP), where the goal is to find a shortest path between $…