1 citations · 1 across the 7 of their papers we have counts for
9 papers
Cardinal Grid Slime Trail is PSPACE-Complete
Anne Pham, Matthew Ferland
Slime Trail is a two-player combinatorial game in which the players alternately move a shared token to an adjacent vertex, permanently removing each vertex the token leaves, while…
A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers
Kyle Burke, Matthew Ferland, Svenja Huntemann +1
In this paper, we address a natural question at the intersection of combinatorial game theory and computational complexity: "Can a sum of simple tepid games in canonical form be in…
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…
Nimber-Preserving Reductions and Homomorphic Sprague-Grundy Game Encodings
Kyle Burke, Matthew Ferland, Shanghua Teng
The concept of nimbers--a.k.a. Grundy-values or nim-values--is fundamental to combinatorial game theory. Nimbers provide a complete characterization of strategic interactions among…
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…