# Examples of $2^{\Theta(n^2)}\text{poly}(n)$-time algorithms

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

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.
• 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 Jul 19 '14 at 3:51