@TechReport{	  it:2002-008,
  author	= {Henrik Bj{\"o}rklund and Sergei Vorobyov},
  title		= {Two Adversary Lower Bounds for Parity Games},
  institution	= {Department of Information Technology, Uppsala University},
  department	= {Computing Science Division},
  year		= {2002},
  number	= {2002-008},
  month		= feb,
  abstract	= {By using the adversary arguments we settle the first
		  exponential lower bounds for restricted classes of
		  algorithms solving Parity Games The first result applies to
		  any algorithms that rely only on estimating values of
		  vertices from the viewpoint of one player and ignore the
		  game graph structure (a rough abstraction of different
		  fix-point algorithms), the second settles the lower bound
		  for a randomized algorithm that samples from the set of
		  optimal counterstrategies (a popular idea used in many
		  approaches). }
}