I thought one of those links was going to be "Parity Lost and Parity Regained", but no? One of them is by the same authors, on the same topic, from the proceedings of the same conference, but it's a different paper? Weird.

http://research.cs.wisc.edu/adsl/Publications/parity-fast08....