Technical Report 2002-008

Two Adversary Lower Bounds for Parity Games

Henrik Björklund and Sergei Vorobyov

February 2002

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).

Available as Postscript (731 kB)

Download BibTeX entry.