Time: 12:00 noon Tuesday, 6th September 2016.
Location: SIT 459
Speaker: Abdallah Saffidine, UNSW
Title: On the Complexity of Connection Games
Invented in 1942, Hex is a strategy game with a lasting influence in board game design as well as in computer games research. In the first part of this talk, we study three related connection games among the most widely played: Havannah, Twixt, and Slither. Drawing inspiration from results on Hex, we examine the complexity of determining the outcome of arbitrary input positions. Back to Hex, we adopt a parameterized complexity perspective and establish that while Short Hex is FPT, Short Generalized Hex is W-complete. In doing so, we disprove a 1999-conjecture by Downey and Fellows in the most influential textbook in parameterized complexity.
This talk is based on joint work with Édouard Bonnet and Florian Jamain appearing in the journal “Theoretical Computer Science” as well as ongoing work with Serge Gaspers, Antonin Lambilliotte, and Stefan Rümmele.
Abdallah Saffidine is an ARC DECRA Fellow and a Research Associate at the University of New South Wales, Sydney, Australia. He works in the Artificial Intelligence and Algorithms groups. He arrived at UNSW in 2013 as a postdoc with Pr. Michael Thielscher and obtained his PhD from the Université Paris-Dauphine, France, under the supervision of Pr. Tristan Cazenave. Abdallah has a wide range of interests from games, planning, and other areas of decision-making to logic, complexity and other areas of theory.