A subexponential lower bound for the Random Facet algorithm for Parity Games
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (2011) - Comments
doi: 10.1137/1.9781611973082.19 

Oliver Friedmann, Thomas Dueholm Hansen, Uri Zwick