BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1537
DTSTAMP:20250424T101721Z
SUMMARY:Complexity of imperfect recall games
DESCRIPTION:Speaker: B. Srivathsan (Chennai Mathematical Institute)\n\nAbst
 ract: \nWe look at two player zero-sum games played on trees. When players
  have perfect information about their state of the game\, finding max-min 
 strategies is easily done by a bottom-up scan of the game-tree. If players
  do not have perfect information about the state of the game\, but still\,
  they remember their own history of actions\, they are said to have perfec
 t recall. Max-min strategies in perfect recall games can be synthesized in
  polynomial-time. When players forget even their own history of actions\, 
 they are said to have imperfect recall. Solving imperfect recall games is 
 known to be NP-hard.In this talk\, we will present new complexity results 
 for imperfect recall games: firstly\, we show that they are as hard as sol
 ving certain problems in the first order theory or reals\, and secondly\, 
 we propose new polynomial-time solvable fragments of imperfect recall game
 s.Joint work with Hugo Gimbert\, Kristoffer Arnsfelt Hansen and Soumyajit 
 Paul.\nShort Bio:\nB Srivathsan is a faculty member at the Chennai Mathema
 tical Institute. He earned his PhD from the University of Bordeaux\, and h
 is Masters and Bachelors from IIT Bombay. His research interests lie in th
 e areas of automata theory\, games and formal verification. \n
URL:https://www.tcs.tifr.res.in/web/events/1537
DTSTART;TZID=Asia/Kolkata:20250506T160000
DTEND;TZID=Asia/Kolkata:20250506T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR