<p>In the PRAM model <em>without bit operations</em>, fairly strong lower bounds are known. For example, in this model, one cannot solve min-cut in $O(\sqrt{n})$ time on $2^{O(\sqrt{n})}$ processors [1]. </p>

<p>Despite being a restricted model, it is strong enough to compute the determinant efficiently, and includes most standard algorithms for poly-time combinatorial optimization problems. See <a href="https://cstheory.stackexchange.com/a/19318/129">here</a>, <a href="https://cstheory.stackexchange.com/a/22471/129">here</a>, or the original paper for more details.</p>

<p>[1] Mulmuley, K. <a href="http://dx.doi.org/10.1137/S0097539794282930" rel="nofollow noreferrer">Lower Bounds in a Parallel Model without Bit Operations</a>. SIAM J. Comput., 28(4), 1460–1509, 1999. (<a href="http://gct.cs.uchicago.edu/lower-bound.ps" rel="nofollow noreferrer">from author's webpage without paywall</a>)</p>

CC BY-SA 3.0
2015-11-23T03:54:53.197Z
2015-11-23T03:54:53.197Z
2017-04-13T12:32:28.167Z
Joshua Grochow
<p>Are there any non-trivial lower bounds on the running time of graph algorithms in RAM/PRAM/
models of computation ? I am not looking for the NP-Hardness results here.</p>

<p>Following is a result that I could find [see ref L92]:</p>

<ul>
<li>3-Coloring of an n-cycle requires $\Omega(\log^*{n})$ time.</li>
</ul>

<p>I was curious to know whether there has been any progress/work in the direction of getting
lower bounds for problems like: Shortest Paths(with/without negative weights), Mincut, 
s-t Maximum flows, Maximum (cardinality/weighted) matching. Any references related to
this are very much appreciated and helpful.</p>

<p><strong>Reference</strong></p>

<p>[ <strong>L92</strong> ] N. Linial, Locality in distributed graph algorithms, SIAM Journal on Com-
puting, 1992, 21(1), pp. 193-201</p>

<p><strong>EDIT:</strong> As suggested by Robin Kothari in the comments, I am making the question more directed.</p>

CC BY-SA 3.0
2012-06-27T14:17:37.840Z
Without restricting the model, an adequate answer to this question could go on for pages. Besides the restriction to graph problems, this question is basically asking "What lower bounds are known in CS?" And the restriction to graph problems isn't a strong one, since in models in which we can prove good lower bounds for some problem (e.g., streaming, decision trees, communication complexity), we can prove good lower bounds for graph problems too.
Robin Kothari
CC BY-SA 3.0
2012-06-27T17:05:52.487Z
@RobinKothari I have edited the question now I am looking for lower bounds in PRAM/RAM models. Do you suggest any more changes?
rizwanhudda
<cc.complexity-theory><reference-request><graph-algorithms><lower-bounds>
Lower Bounds on Running time of Graph Algorithms
rizwanhudda
# Lower Bounds on Running time of Graph Algorithms

(Asked by: username_0 on 2012-06-27)

Are there any non-trivial lower bounds on the running time of graph algorithms in RAM/PRAM/
models of computation ? I am not looking for the NP-Hardness results here.

Following is a result that I could find [see ref L92]:

* 3-Coloring of an n-cycle requires $\Omega(\log^\*{n})$ time.

I was curious to know whether there has been any progress/work in the direction of getting
lower bounds for problems like: Shortest Paths(with/without negative weights), Mincut,
s-t Maximum flows, Maximum (cardinality/weighted) matching. Any references related to
this are very much appreciated and helpful.

**Reference**

[ **L92** ] N. Linial, Locality in distributed graph algorithms, SIAM Journal on Com-
puting, 1992, 21(1), pp. 193-201

**EDIT:** As suggested by Robin Kothari in the comments, I am making the question more directed.

**Tags:** cc.complexity-theory, reference-request, graph-algorithms, lower-bounds
> **Comments:**
> **username_1**: Without restricting the model, an adequate answer to this question could go on for pages. Besides the restriction to graph problems, this question is basically asking "What lower bounds are known in CS?" And the restriction to graph problems isn't a strong one, since in models in which we can prove good lower bounds for some problem (e.g., streaming, decision trees, communication complexity), we can prove good lower bounds for graph problems too.  
> **username_0**: @RobinKothari I have edited the question now I am looking for lower bounds in PRAM/RAM models. Do you suggest any more changes?  

---

## 1 answers

### Answer by username_2 on 2015-11-23. Score: 3

In the PRAM model *without bit operations*, fairly strong lower bounds are known. For example, in this model, one cannot solve min-cut in $O(\sqrt{n})$ time on $2^{O(\sqrt{n})}$ processors [1].

Despite being a restricted model, it is strong enough to compute the determinant efficiently, and includes most standard algorithms for poly-time combinatorial optimization problems. See [here](https://cstheory.stackexchange.com/a/19318/129), [here](https://cstheory.stackexchange.com/a/22471/129), or the original paper for more details.

[1] Mulmuley, K. [Lower Bounds in a Parallel Model without Bit Operations](http://dx.doi.org/10.1137/S0097539794282930). SIAM J. Comput., 28(4), 1460–1509, 1999. ([from author's webpage without paywall](http://gct.cs.uchicago.edu/lower-bound.ps))


---

