Powerful Algorithms too complex to implement

What are some algorithms of legitimate utility that are simply too complex to implement? Let me be clear: I'm not looking for algorithms like the current asymptotic optimal matrix multiplication algorithm (Coppersmith-Winograd), which is reasonable to implement but has a constant that makes it useless in practice. I'm looking for algorithms that could plausibly have practical value, but are so difficult to code that they have never been implemented, only implemented in extremely artificial settings, or only implemented for remarkably special-purpose applications. Also welcome are near-impossible-to-implement algorithms that have good asymptotics but would likely have poor real performance.