Skip to content

LAA

Seminar

Games as an algorithmic construct

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

Seminar Room 1, Newton Institute

Abstract

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

Presentation

[ps  ]

Audio

MP3MP3 Real AudioReal Audio

Back to top ∧