Virginia Vassilevska Williams
where else to find them
no profile links on file
what they talk about
where they keep going back
no series more than once — all 5 in the filters
on a stage with
- Hung Leonce
- Lazar Milenkoviconce
- Shay Solomononce
who talks about the same things
nobody close enough yet
| title | conference | date |
|---|---|---|
| Fine-Grained Complexity 1 | Logic and Algorithms in Database Theory and AI Boot Camp | 2023-08-21 |
Fine-grained complexity pins concrete running-time hypotheses (SETH: no 2^{n(1−ε)} SAT, 3SUM: no n^{2−o(1)}, APSP: no n^{3−o(1)}) and proves many practical… | ||
| Fine-Grained Complexity 3 | Logic and Algorithms in Database Theory and AI Boot Camp | 2023-08-21 |
Shows simple reductions that turn OV/3OV/OMv assumptions into tight dynamic lower bounds: single-source reachability, SCC count and diameter each get nd =… | ||
| Dynamic Matching Algorithms Under Vertex Updates | ITCS 2022 | 2022-01-31 |
Maintains maximal matchings under vertex insertions and deletions with a concrete tradeoff: a simple bipartite algorithm (one side fixed) is irrevocable and… | ||
| Computational Complexity of Polynomial Time Problems: Introduction | Fine-Grained Complexity and Algorithm Design Boot Camp 2015 | 2015-08-31 |
Overview of fine-grained complexity that pins down why many polynomial-time problems resist improvement: conjectures named are ETH/SETH, 3SUM, orthogonal… | ||
| Hardness for Graph Problems - Reductions Based on APSP and SETH | Fine-Grained Complexity and Algorithm Design Boot Camp 2015 | 2015-08-31 |
Dense-case claim: APSP-equivalent to radius/median/eccentricities via fine-grained, sometimes adaptive reductions that build min-plus (distance) products and… | ||
| Hardness for Sequence Problems - LCS and Frechet Distance | Fine-Grained Complexity and Algorithm Design Boot Camp 2015 | 2015-08-31 |
Reduction from Orthogonal Vectors produces two sequences X,Y of length N·poly(d) (construction time N·poly(d)) so LCS, edit distance, DTW and Fréchet are… | ||
| Hardness for Dynamic Problems; Conclusion and Future Research | Fine-Grained Complexity and Algorithm Design Boot Camp 2015 | 2015-08-31 |
Shows concrete reductions: maps an orthogonal vectors instance (n vectors in d dimensions) to a dynamic single‑source reachability instance with about n·d… | ||
| Matrix Multiplication: Coppersmith-Winograd and Beyond | Tensors in Computer Science and Geometry 2014 | 2014-11-10 |
Describes a concrete route from tensors to matrix multiplication exponent: use border rank q+2 bounds on a specific Coppersmith‑Winograd family, symmetrize and… | ||
| Matrix Multiplication | Algorithms and Complexity in Algebraic Geometry Boot Camp 2014 | 2014-09-02 |
Asks how fast N×N multiplication can be done and connects concrete algebraic claims to algorithms: uses rank vs border rank (Strassen shows 2×2 rank ≤7; a… | ||
| nothing matches | ||