As of May 31, 2023, we have updated our Code of Conduct.

Questions tagged [fine-grained-analysis]

Analyzing the asymptotic complexity of problems already known to be polynomial time solvable. Often, conditional lower bounds are used to show that a specific algorithm is asymptotically optimal.

Filter by
Sorted by
Tagged with
3 votes
0 answers

Can fine-grained hardness be proved directly from classical hardness (e.g., $\sf P \neq NP$) in some way?

I have just learnt about some typical result of fine-grained hardness in 15-455 by Prof Ryan: CNF-SETH implies ${\sf DIAMETER} \notin {\sf TIME}(mn^{1-\epsilon})$. (Here DIAMETER stands for the graph ...
Marcythm's user avatar
  • 301
6 votes
1 answer

An example where the algorithm of Hopcroft and Karp performs poorly?

I have been trying to construct an example, where Hopcroft and Karp's algorithm for the maximum matching problem performs poorly (say at least $\Omega(\log n)$ rounds). However, all the examples I ...
Narek Bojikian's user avatar
4 votes
1 answer

Conditional lower bounds on the running time of the single source shortest path problem

Just out of curiosity, I was wondering whether there is a conditional lower-bound on the running time of an algorithm for the Single Source Shortest Path Problem (on directed or undirected graphs). I ...
Narek Bojikian's user avatar