[mihaild]

For example, there is 0.8776-approximation that runs in about O(n^{10^100}) https://arxiv.org/abs/1205.0458v2 There are also a lot of graph problems like "distinguish 3-colorable graph from graph that can't be colored in 3 colors even after removing eps part of edges" with large polynomials (IIRC, we got something like O(n^{2^40000}) when tried to find degree explicitly).