Source author record

Mina Dalirrooyfard

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity

Catalog footprint

Research overview

2works

2topics

2close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Conditionally optimal approximation algorithms for the girth of a directed graph

It is known that a better than $2$ -approximation algorithm for the girth in dense directed unweighted graphs needs $n^{3-o(1)}$ time unless one uses fast matrix multiplication. Meanwhile, the best known approximation factor for a combinatorial algorithm running in $O(mn^{1-ε})$ time (by Chechik et al.) is $3$ . Is the true answer $2$ or $3$ ? The main result of this paper is a (conditionally) tight approximation algorithm for directed graphs. First, we show that under a popular hardness assumption, any algorithm, even one that exploits fast matrix multiplication, would need to take at least $mn^{1-o(1)}$ time for some sparsity $m$ if it achieves a $(2-ε)$ -approximation for any $ε>0$ . Second we give a $2$ -approximation algorithm for the girth of unweighted graphs running in $\tilde{O}(mn^{3/4})$ time, and a $(2+ε)$ -approximation algorithm (for any $ε>0$ ) that works in weighted graphs and runs in $\tilde{O}(m\sqrt n)$ time. Our algorithms are combinatorial. We also obtain a $(4+ε)$ -approximation of the girth running in $\tilde{O}(mn^{\sqrt{2}-1})$ time, improving upon the previous best $\tilde{O}(m\sqrt n)$ running time by Chechik et al. Finally, we consider the computation of roundtrip spanners. We obtain a $(5+ε)$ -approximate roundtrip spanner on $\tilde{O}(n^{1.5}/ε^2)$ edges in $\tilde{O}(m\sqrt n/ε^2)$ time. This improves upon the previous approximation factor $(8+ε)$ of Chechik et al. for the same running time.

preprint2020arXiv

New Techniques for Proving Fine-Grained Average-Case Hardness

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$ SUM and zero- $k$ -clique that are both worst-case and average-case fine-grained hard assuming the core hypotheses of FGC. We then use these as a basis for fine-grained hardness and average-case hardness of other problems. The new problems represent their inputs in a certain ``factored'' form. We call them ``factored''-OV, ``factored''-zero- $k$ -clique and ``factored''- $3$ SUM. We show that factored- $k$ -OV and factored $k$ SUM are equivalent and are complete for a class of problems defined over Boolean functions. Factored zero- $k$ -clique is also complete, for a different class of problems. Our hard factored problems are also simple enough that we can reduce them to many other problems, e.g.~to edit distance, $k$ -LCS and versions of Max-Flow. We further consider counting variants of the factored problems and give WCtoACFG reductions for them for a natural distribution. Through FGC reductions we then get average-case hardness for well-studied problems like regular expression matching from standard worst-case FGC assumptions. To obtain our WCtoACFG reductions, we formalize the framework of [Boix-Adsera et al. 2019] that was used to give a WCtoACFG reduction for counting $k$ -cliques. We define an explicit property of problems such that if a problem has that property one can use the framework on the problem to get a WCtoACFG self reduction. We then use the framework to slightly extend Boix-Adsera et al.'s average-case counting $k$ -cliques result to average-case hardness for counting arbitrary subgraph patterns of constant size in $k$ -partite graphs...

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.