5 papers · 1 filter
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-…
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…
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…
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…