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

<p>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.</p>

CC BY-SA 2.5
2011-01-26T16:44:37.213Z
2011-01-26T16:44:37.213Z
Sariel Har-Peled
<p>I think the paper "<a href="http://www.cs.cmu.edu/~ryanw/tria-mmult.pdf">Subcubic Equivalences Between Path, Matrix, and Triangle
Problems</a>" by V. Vassilevska Williams and R. Williams is what you're looking for. Its abstract contains the list of the following problems on graphs:</p>

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

<p>According to the abstract the paper is about the following:</p>

<blockquote>
  <p>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.</p>
</blockquote>

CC BY-SA 2.5
2011-01-27T04:46:03.107Z
But see also Timothy Chan's subcubic APSP algorithm, which does NOT play bit games: http://www.springerlink.com/content/px2741688g4p4l18/
Jeffε
CC BY-SA 2.5
2011-01-26T17:32:53.587Z
2011-01-26T20:24:36.143Z
2011-01-26T20:24:36.143Z
Oleksandr Bondarenko
<p>This is intended as a follow up question to Robin Kothari's previous post on <a href="https://cstheory.stackexchange.com/questions/1284/problems-that-can-be-used-to-show-polynomial-time-hardness-results">polynomial time hardness results</a>.</p>
<p>Specifically, I'm interested in seeing some hardness proofs for problems that are believed to have roughly <span class="math-container">$\Omega(n^3)$</span> 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. <a href="https://doi.org/10.1007/11534273_36" rel="nofollow noreferrer">[via Springer]</a>). I would be happy to keep problems in the decision tree model if it simplifies the responses.</p>
<p>From Robin's post, I learned about Jeff Erikson's <a href="http://cjtcs.cs.uchicago.edu/articles/1999/8/cj99-08.pdf" rel="nofollow noreferrer">paper</a> which gives a <span class="math-container">$\Omega(n^3)$</span> lower bound for 5SUM (more accurately, he shows that <span class="math-container">$k$</span>-SUM runs in <span class="math-container">$\Omega (n^{\lceil k/2 \rceil})$</span> time in general).</p>
<p>Do papers or other references exist using such reductions to conjecture cubic lower bounds for problems in computational geometry or graph theory?</p>

CC BY-SA 2.5
2011-03-02T19:00:15.577Z
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.
Bob Fraser
<graph-theory><cg.comp-geom><lower-bounds>
Which problems in computational geometry or graph theory are believed to be $\Omega(n^3)$?
Bob Fraser
# Which problems in computational geometry or graph theory are believed to be $\Omega(n^3)$?

(Asked by: username_0 on 2011-01-26)

This is intended as a follow up question to Robin Kothari's previous post on [polynomial time hardness results](https://cstheory.stackexchange.com/questions/1284/problems-that-can-be-used-to-show-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]](https://doi.org/10.1007/11534273_36)). 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](http://cjtcs.cs.uchicago.edu/articles/1999/8/cj99-08.pdf) 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?

**Tags:** graph-theory, cg.comp-geom, lower-bounds

> **Comments:**
> **username_0**: 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.  

---

## 2 answers

### Answer by username_2 on 2011-01-26. Score: 15 | Accepted answer

I think the paper "[Subcubic Equivalences Between Path, Matrix, and Triangle
Problems](http://www.cs.cmu.edu/~ryanw/tria-mmult.pdf)" 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.

> **Comments:**
> **username_3**: But see also Timothy Chan's subcubic APSP algorithm, which does NOT play bit games: http://www.springerlink.com/content/px2741688g4p4l18/  

---

### Answer by username_1 on 2011-01-26. Score: 9

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.


---

