Which problems in computational geometry or graph theory are believed to be $\Omega(n^3)$?

Question

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?

Answer 1

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.

Answer 2

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.