~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
CCS Seminar
Friday - April 13, 2007
12:00 noon
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Physics Research Building - Room 595
Kyle Burke
Computer Science Department - Boston University
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*"Games on the Sperner Triangle"
*
Using the mathematical constructs of Emanuel Sperner, we present a simple
two-player game in which ties are not possible. Although the rules are very
straight-forward, we show that it is computationally difficult 
(PSPACE-hard)
to determine optimal strategies for game play. In this talk we will 
describe the
game, explain Sperner's Lemma and prove the hardness result. Given time,
we will talk about the forthcoming result that an easy version of the 
game exists
after only a slight tweak in the rules.

http://ccs.bu.edu

Created for the Boston University/SCV Projects Page.

Created by The CoCoBoard.