The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content



Games as an algorithmic construct

Vardi, M (Rice)
Wednesday 05 July 2006, 09:00-10:25

Seminar Room 1, Newton Institute


Games were introduced into complexity theory by Chandra, Kozen, and Stockmeyer (JACM, 198), through the concept of alternation, which generalizes nondeterminism. The standard use of alternation is in complexity-theoretic settings. The focus of this talk is on presenting games and alternation as a powerful algorithmic construct. The driving examples are various automated-verification tasks, where games yield elegant and optimal algorithms.

Related Links


[ps  ]


MP3MP3 Real AudioReal Audio

Back to top ∧