10
$\begingroup$

In recent years, there has been exciting work in proving lower bounds for polynomial-time problems conditional on conjectures like SETH or "All-Pairs-Shortest-Paths (APSP) cannot be solved in $O(|V|^{3-\epsilon})$ time" and others.

Now suppose we have a problem whose input data is naturally arranged in an $m\times n$ array, and there is a plausibly-optimal known $O(m^2n)$ algorithm solving it. Are there any techniques around that could be used to prove matching (conditional) lower bounds of this form?

The existing results seem to me to mainly focus on "1-dimensional" running times, i.e. proving optimality of time quadratic-in-input-length or cubic-in-input-length (or alternatively in the number of vertices of a graph, but assuming it to be either dense or sparse).

Improve this question
$\endgroup$
1
  • 4
    $\begingroup$ There are some recent works which prove conditional lower bounds for several parameters. For example, $\Omega( (nm)^{1-\epsilon}) bound in Theorem 1.3 in arxiv.org/pdf/1502.01063v2.pdf. Moreover, in this video simons.berkeley.edu/talks/… , Karl consider 7 parameters(!) for LCS problem. $\endgroup$
    – Thatchaphol
    Commented Dec 23, 2015 at 10:10

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.