Planar Perfect Matching is "not" in NC

I though I get close to actually solving the planar matching problem in NC. We had a simultaneous arXiv submission on this problem together with Vijay Vazirani and Nima Anari. However, my solution contained a major error. Hence, with regret I need to say that my paper does not show that planar perfect matching is in NC.

Congratulations Vijay and Nima on your solution! Great to see that this intriguing problem has been finally solved.

One thought on “Planar Perfect Matching is "not" in NC

Leave a Reply

Your email address will not be published. Required fields are marked *