@TechReport{	  it:2000-014,
  author	= {Sergei Vorobyov},
  title		= {Better Decision Algorithms for Parity Games and the
		  Mu-Calculus Model Checking},
  institution	= {Department of Information Technology, Uppsala University},
  department	= {Computing Science Division},
  year		= {2000},
  number	= {2000-014},
  month		= jun,
  abstract	= {We suggest an algorithm with the asymptotically best
		  behavior among currently known algorithms for the problems
		  enumerated in the title, when the number of alternations
		  $k$ is $\Omega(n^{\frac{1}{2}+\varepsilon})$, where $n$ is
		  the number of states and $0<\varepsilon\leq\frac{1}{2}$.
		  The best previously known algorithm
		  \cite{BrowneClarkeJhaLongMarrero97} runs in time
		  $O(k^2\cdot n\cdot \sqrt{n}^k)$ and uses approximately the
		  same space. For comparison, our algorithm for $k=n$ (the
		  most difficult case) runs in time $O(n^3\cdot (1.61803)^k)$
		  and uses a small polynomial space. We also show, for the
		  first time, that there is a \emph{subexponential}
		  randomized algorithms for the problem when
		  $k=\Omega(n^{\frac{1}{2}+\varepsilon})$. It was an open
		  problem as to whether such algorithms exist at all. }
}