8 papers
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…
Distributed Distance Approximation
Bertie Ancona, Keren Censor-Hillel, Mina Dalirrooyfard +2
Diameter, radius and eccentricities are fundamental graph parameters, which are extensively studied in various computational settings. Typically, computing approximate answers can…
Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs
Mina Dalirrooyfard, Nicole Wein
Among the most fundamental graph parameters is the Diameter, the largest distance between any pair of vertices. Computing the Diameter of a graph with edges requires $m^{2-o(1)…
New Techniques for Proving Fine-Grained Average-Case Hardness
Mina Dalirrooyfard, Andrea Lincoln, Virginia Vassilevska Williams
The recent emergence of fine-grained cryptography strongly motivates developing an average-case analogue of Fine-Grained Complexity (FGC). This paper defines new versions of OV, $k…
Conditionally optimal approximation algorithms for the girth of a directed graph
Mina Dalirrooyfard, Virginia Vassilevska Williams
It is known that a better than -approximation algorithm for the girth in dense directed unweighted graphs needs time unless one uses fast matrix multiplication. Mea…
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas +1
Some of the most fundamental and well-studied graph parameters are the Diameter (the largest shortest paths distance) and Radius (the smallest distance for which a "center" node ca…