| Title | : | Counting winning strategies in two player games: theory and practice |
| Speaker | : | Vaibhav Krishan (IMSc, Chennai) |
| Details | : | Wed, Jul 22, 2026 11:30 AM, @ SSB 334 |
| Abstract | : | Practical systems routinely solve problems that are theoretically intractable.
A prominent example is the Quantified Boolean Formula (QBF) problem, which asks whether a player has a winning strategy in a finite two-player game.
Despite being PSPACE-complete, QBF is a powerful modeling framework for applications including planning, model checking, reactive synthesis, and reasoning about multi-agent systems. In this talk, I will focus on counting winning strategies in such games. I will present a practical system that efficiently solves important instances of this problem, discuss the theoretical foundations underlying its design, and show how recent theoretical advances can guide the development of more effective practical solvers. The talk is based on joint work with Sravathi Chede, Leroy Chew, and Anil Shukla (to appear at SAT 2026), as well as ongoing work with Sravathi Chede, Swagato Sanyal, and Anil Shukla. Speaker Bio: Vaibhav is a postdoctoral fellow at IMSc, Chennai. He completed his PhD from CSE Dept at IITB, supervised by Prof. Sundar Vishwanathan and Prof. Nutan Limaye. |