Perfect Matching in Random Graphs is as Hard as Tseitin.

Per Austrin, Kilian Risse

Browse the full SODA paper archive.