Deterministic Parallel algorithm for perfect matching in general graphs? In complexity class $\mathsf{P}$, there are some problems conjectured NOT to be in the class $\mathsf{NC}$, i.e. problems with deterministic parallel algorithms. Maximum Flow problem is one example. And there are problems BELIEVED to be in $\mathsf{NC}$, but a proof is not found yet. 

Perfect Matching problem is one of the most fundamental problem raised in graph theory: given a graph $G$, we have to find a perfect matching for $G$. As I could found on the internet, despite of the beautiful polynomial time Blossom algorithm by Edmonds, and a RANDOMIZED parallel algorithm by Karp, Upfal and Wigderson in 1986, only a few subclasses of graphs are known to have $\mathsf{NC}$ algorithms. 

In Jan. 2005 there's a post in the blog Computational Complexity that claims it remains open whether Perfect Matching is in $\mathsf{NC}$. My question is:


  Is there any progress since then, beyond the randomized $\mathsf{NC}$ algorithm?


To clarify my interest, any algorithm which deals with GENERAL graphs are nice. Although algorithms for subclasses of graphs are OK too, that may be not on my attentions. Thank you all!



EDIT at 12/27:

Thank you for all your help, I try to summarize all the results in one figure:


The lowest known classes contain the following problems:


Matching in general graphs: $\mathsf{RNC}$ [KUW86], $\mathsf{RNC}^2$ [CRS93]
Matching in bipartite planar/constant genus graphs: $\mathsf{UL}$/$\mathsf{SPL}$ [DKT10]/[DKTV10]
Matching when the total number is polynomial: $\mathsf{SPL}$ [H09]
Lex-first maximal matching: $\mathsf{CC}$ [MS89]


Furthermore, under plausible complexity assumption: $\mathsf{SPACE[n]}$ requires exponential circuits, Matching in general graphs is in $\mathsf{SPL}$ [ARZ98].
$NC$ algorithms for perfect matchings in general graphs is still open but there has been some progress. Here are a few that I am aware of:

For general graphs, Agrawal-Hoang-Thierauf showed that given the promise that the number of perfect matchings is small, there is an $NC^2$ algorithm to enumerate all of them. 

For the class of planar graphs, the pfaffian plays a big role. Kastelyn showed how every planar graph can be oriented in a way such that the pfaffian exactly equals the number of perfect matchings. (This was used by Valiant in to give "Holographic algorithms" for various problems) Mahajan-Subramanya-Vinay showed how the pfaffian can be computed in $NC$ using modifications of clow sequences. (Kastelyn in fact gives an algorithm to find the embedding in $P$ but I'm not sure if the pfaffian embedding can also be computed in $NC$; if yes, that would mean that counting perfect matchings in planar graphs is in $NC$.)

And a recent result of Vinodchandran-Tewari show that the isolation lemma can be "derandomized" for planar graphs (using Green's theorem!) to put planar reachability in $UL$. But $NC$ algorithms for planar matchings are still open (thanks to Raghunath for correcting my claim that it is in $UL$). An $NC$ algorithm for bipartite planar matchings was given by Datta-Kulkarni-Roy

Hope this helps.