1 citations · 1 across the 5 of their papers we have counts for
6 papers
NP-Hardness of a 2D, a 2.5D, and a 3D Puzzle Game
Matthew Ferland, Vikram Kher
In this paper, we give simple NP-hardness reductions for three popular video games. The first is Baba Is You, an award winning 2D block puzzle game with the key premise being the a…
Winning the War by (Strategically) Losing Battles: Settling the Complexity of Grundy-Values in Undirected Geography
Kyle Burke, Matthew Ferland, Shanghua Teng
We settle two long-standing complexity-theoretical questions-open since 1981 and 1993-in combinatorial game theory (CGT). We prove that the Grundy value (a.k.a. nim-value, or nimbe…
Transverse Wave: an impartial color-propagation game inspired by Social Influence and Quantum Nim
Kyle Burke, Matthew Ferland, Shanghua Teng
In this paper, we study a colorful, impartial combinatorial game played on a two-dimensional grid, Transverse Wave. We are drawn to this game because of its apparent simplicity, co…
Quantum Combinatorial Games: Structures and Computational Complexity
Kyle Burke, Matthew Ferland, Shang-Hua Teng
Recently, a standardized framework was proposed for introducing quantum-inspired moves in mathematical games with perfect information and no chance. The beauty of quantum games-suc…
Computational Properties of Slime Trail
Matthew Ferland, Kyle Burke
We investigate the combinatorial game Slime Trail.This game is played on a graph with a starting piece in a node. Each player's objective is to reach one of their own goal nodes. E…
Quasar Metal Abundances and Host Galaxy Evolution
Fred Hamann, Craig Warner, Matthias Dietrich +1
Quasars signal a unique phase of galaxy evolution -- when massive spheroids are rapidly being assembled, forming stars and growing their central super-massive black holes. Measurem…