13 papers
Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More
Mina Dalirrooyfard, Andrea Lincoln, Barna Saha +1
This work establishes conditional lower bounds for average-case {\em parity}-counting versions of the problems -XOR, -SUM, and -OV. The main contribution is a set of self-…
On Diameter Approximation in Directed Graphs
Amir Abboud, Mina Dalirrooyfard, Ray Li +1
Computing the diameter of a graph, i.e. the largest distance, is a fundamental problem that is central in fine-grained complexity. In undirected graphs, the Strong Exponential Time…
Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
Mina Dalirrooyfard, Surya Mathialagan, Virginia Vassilevska Williams +1
We study finding and listing -cliques in a graph, for constant , a fundamental problem of both theoretical and practical importance. Our main contribution is a new outp…
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…
Hardness of Approximate Diameter: Now for Undirected Graphs
Mina Dalirrooyfard, Ray Li, Virginia Vassilevska Williams
Approximating the graph diameter is a basic task of both theoretical and practical interest. A simple folklore algorithm can output a 2-approximation to the diameter in linear time…
Approximation Algorithms for Min-Distance Problems in DAGs
Mina Dalirrooyfard, Jenny Kaufmann
The min-distance between two nodes is defined as the minimum of the distance from to or from to , and is a natural distance metric in DAGs. As with the standa…
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…
Graph pattern detection: Hardness for all induced patterns and faster non-induced cycles
Mina Dalirrooyfard, Thuy Duong Vuong, Virginia Vassilevska Williams
We consider the pattern detection problem in graphs: given a constant size pattern graph and a host graph , determine whether contains a subgraph isomorphic to . Our…
Approximation Algorithms for Min-Distance Problems
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas +3
We study fundamental graph parameters such as the Diameter and Radius in directed graphs, when distances are measured using a somewhat unorthodox but natural measure: the distance…