@TechReport{	  it:2001-001,
  author	= {Viktor Petersson and Sergei Vorobyov},
  title		= {A Randomized Subexponential Algorithm for Parity Games},
  institution	= {Department of Information Technology, Uppsala University},
  department	= {Computing Science Division},
  year		= {2001},
  number	= {2001-001},
  month		= jan,
  abstract	= {We describe a randomized algorithm for \textsc{Parity
		  Games} (equivalent to the \textsc{Mu-Calculus Model
		  Checking}), which runs in expected time
		  $2^{O(k^{1/(1+2\varepsilon)})}$ \emph{subexponential} in
		  the number of colors $k$ of the game graph when $k$ is
		  $\Omega(n^{1/2+\varepsilon})$, $n$ is the number of
		  vertices, and $0<\varepsilon\leq 1/2$.
		  
		  All previously known algorithms were \emph{exponential} in
		  the number of colors, with the best one taking time and
		  space $O(k^2\cdot n\cdot \sqrt{n}^k)$.
		  
		  Our algorithm does not rely on Linear Programming
		  subroutines and uses a low-degree polynomial space. }
}