0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ The wiki page says that Collins algorithm is doubly exponential--that is, of the form $a^{b^n}$ for some $a$ and $b$. $\endgroup$ – Austin Buchanan Jul 19 '14 at 3:51
  • $\begingroup$ It is lower for special cases... $\endgroup$ – Sariel Har-Peled Jul 20 '14 at 4:46
  • $\begingroup$ Ok. I updated my answer... $\endgroup$ – Sariel Har-Peled Jul 20 '14 at 16:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.