<p>New answer:
The number of pseudo line arrangements is 2^{Theta(n^2)} <a href="http://page.math.tu-berlin.de/~felsner/Paper/numarr.pdf" rel="nofollow">http://page.math.tu-berlin.de/~felsner/Paper/numarr.pdf</a> . Which is in turn can be used to bound the number order type of n points in the plane. Thus if you want to check some concrete conjecture on point configurations in the plane, you are going to get your desired running time. Examples of algorithms using this approach and use this approach are here: <a href="http://www.ist.tugraz.at/aichholzer/research/rp/triangulations/ordertypes/" rel="nofollow">http://www.ist.tugraz.at/aichholzer/research/rp/triangulations/ordertypes/</a> . If you do not aggressively cut the search space for the specific conjecture you are checking, you would get the running you want.</p>

<p>In a similar direction, checking if a generic property holds for all binary n*n matrices, would take this running time. This in particular, the time it would take to verify a "generic" property over graphs over n vertices. As a "silly" example, think about a Ramsey type conjecture: Every graph over n vertices contains either a clique or an independent set of size $\Theta(\log n)$. Ha! This running time is explicitly mentioned in the Wikipedia page: <a href="http://en.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numbers" rel="nofollow">http://en.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numbers</a>.</p>

<hr>

<p>Old answer:
Some variants of Cylindrical algebraic decomposition if my memory serves me right.</p>

<p><a href="http://en.wikipedia.org/wiki/Cylindrical_algebraic_decomposition" rel="nofollow">http://en.wikipedia.org/wiki/Cylindrical_algebraic_decomposition</a></p>

CC BY-SA 3.0
2014-07-19T03:51:44.693Z
The wiki page says that Collins algorithm is doubly exponential--that is, of the form $a^{b^n}$ for some $a$ and $b$.
Austin Buchanan
CC BY-SA 3.0
2014-07-20T04:46:17.897Z
It is lower for special cases...
Sariel Har-Peled
CC BY-SA 3.0
2014-07-20T16:12:34.763Z
Ok. I updated my answer...
Sariel Har-Peled
CC BY-SA 3.0
2014-07-19T00:06:17.970Z
2014-07-20T05:31:27.727Z
2014-07-20T05:31:27.727Z
Sariel Har-Peled
<p>What are notable examples of problems for which the best currently known algorithm has $2^{\Theta(n^2)}\text{poly}(n)$ running time ?</p>

<ds.algorithms><exp-time-algorithms>
Examples of $2^{\Theta(n^2)}\text{poly}(n)$-time algorithms
XORwell
# Examples of $2^{\Theta(n^2)}\text{poly}(n)$-time algorithms

(Asked by: username_0 on 2014-07-18)

What are notable examples of problems for which the best currently known algorithm has $2^{\Theta(n^2)}\text{poly}(n)$ running time ?

**Tags:** ds.algorithms, exp-time-algorithms

---

## 1 answers

### Answer by username_1 on 2014-07-19. Score: 2 | Accepted answer

New answer:
The number of pseudo line arrangements is 2^{Theta(n^2)} <http://page.math.tu-berlin.de/~felsner/Paper/numarr.pdf> . Which is in turn can be used to bound the number order type of n points in the plane. Thus if you want to check some concrete conjecture on point configurations in the plane, you are going to get your desired running time. Examples of algorithms using this approach and use this approach are here: <http://www.ist.tugraz.at/aichholzer/research/rp/triangulations/ordertypes/> . If you do not aggressively cut the search space for the specific conjecture you are checking, you would get the running you want.

In a similar direction, checking if a generic property holds for all binary n\*n matrices, would take this running time. This in particular, the time it would take to verify a "generic" property over graphs over n vertices. As a "silly" example, think about a Ramsey type conjecture: Every graph over n vertices contains either a clique or an independent set of size $\Theta(\log n)$. Ha! This running time is explicitly mentioned in the Wikipedia page: <http://en.wikipedia.org/wiki/Ramsey%27s_theorem#Ramsey_numbers>.

---

Old answer:
Some variants of Cylindrical algebraic decomposition if my memory serves me right.

<http://en.wikipedia.org/wiki/Cylindrical_algebraic_decomposition>

> **Comments:**
> **username_2**: The wiki page says that Collins algorithm is doubly exponential--that is, of the form $a^{b^n}$ for some $a$ and $b$.  
> **username_1**: It is lower for special cases...  
> **username_1**: Ok. I updated my answer...  

---

