12
$\begingroup$

This is intended as a follow up question to Robin Kothari's previous post on polynomial time hardness results.

Specifically, I'm interested in seeing some hardness proofs for problems that are believed to have roughly $\Omega(n^3)$ lower bounds, and I say roughly to allow for slightly subcubic improvements by playing with the word size (such as that for 3SUM by Barab et al. [via Springer]). I would be happy to keep problems in the decision tree model if it simplifies the responses.

From Robin's post, I learned about Jeff Erikson's paper which gives a $\Omega(n^3)$ lower bound for 5SUM (more accurately, he shows that $k$-SUM runs in $\Omega (n^{\lceil k/2 \rceil})$ time in general).

Do papers or other references exist using such reductions to conjecture cubic lower bounds for problems in computational geometry or graph theory?

$\endgroup$
  • $\begingroup$ Both of these answers were helpful for me, thanks! Also, Jeff's pointer to Timothy's paper was much appreciated, that is a very nice result. $\endgroup$ – Bob Fraser Mar 2 '11 at 19:00
13
$\begingroup$

I think the paper "Subcubic Equivalences Between Path, Matrix, and Triangle Problems" by V. Vassilevska Williams and R. Williams is what you're looking for. Its abstract contains the list of the following problems on graphs:

  • The all-pairs shortest paths problem on weighted digraphs (APSP).
  • Detecting if a weighted graph has a triangle of negative total edge weight.
  • Listing up to $n^{2.99}$ negative triangles in an edge-weighted graph.
  • The replacement paths problem on weighted digraphs.
  • Finding the second shortest simple path between two nodes in a weighted digraph.

According to the abstract the paper is about the following:

We define a notion of subcubic reducibility, and show that many important problems on graphs and matrices solvable in $O(n^3)$ time are equivalent under subcubic reductions.

$\endgroup$
9
$\begingroup$

One can then use reductions to these problem as starting point to prove lower bounds. See for example section 5 in the following paper: http://valis.cs.uiuc.edu/~sariel/papers/03/lms/lms.pdf. Also section 4 and 5 in the following paper: http://valis.cs.uiuc.edu/~sariel/papers/08/expand_cover/expand_cover.pdf. I am sure there are other examples - this is just papers I worked on and such remember they use such argumentation.

For example, the above prove that given a set of weighted half-spaces in $\Re^5$, finding the minimum weight cover of $\Re^5$ by these half-space requires $\Omega(n^5)$ time.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.