37 citations · 40 across the 14 of their papers we have counts for
16 papers
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…
Forced Capture Hnefatafl
Kyle Burke, Craig Tennenhouse
We define a new, partizan, loopy combinatorial game, Forced-Capture Hnefatafl, similar to Hnefatafl, except that players are forced to make capturing moves when available. We show…
Vexing Vexillological Logic
Kyle Burke, Craig Tennenhouse
We define a new impartial combinatorial game, Flag Coloring, based on flood filling. We then generalize to a graph game, and find values for many positions on two colors. We demons…
Æquitas: Two-Player Counterfeit Coin Games
Kyle Burke, Tanya Khovanova, Joshua Lee +3
We discuss games involving a counterfeit coin. Given one counterfeit coin among a number of otherwise identical coins, two players with full knowledge of the fake coin take turns w…
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…
Single-Player and Two-Player Buttons & Scissors Games
Kyle Burke, Erik D. Demaine, Harrison Gregg +12
We study the computational complexity of the Buttons \& Scissors game and obtain sharp thresholds with respect to several parameters. Specifically we show that the game is NP-compl…
Enhancing semantic expressivity in the cultural heritage domain: exposing the Zeri Photo Archive as Linked Open Data
Marilena Daquino, Francesca Mambelli, Silvio Peroni +2
Describing cultural heritage objects from the perspective of Linked Open Data (LOD) is not a trivial task. The process often requires not only choosing pertinent ontologies, but al…
PSPACE-Complete Two-Color Placement Games
Kyle Burke, Bob Hearn
We show that three placement games, Col, NoGo, and Fjords, are PSPACE-complete on planar graphs. The hardness of Col and Fjords is shown via a reduction from Bounded 2-Player Const…
Quantified Boolean Formula Games and Their Complexities
Kyle Burke
Consider QBF, the Quantified Boolean Formula problem, as a combinatorial game ruleset. The problem is rephrased as determining the winner of the game where two opposing players tak…
Impartial coloring games
Gabriel Beaulieu, Kyle Burke, Eric Duchêne
Coloring games are combinatorial games where the players alternate painting uncolored vertices of a graph one of colors. Each different ruleset specifies that game's colori…
A PSPACE-complete Graph Nim
Kyle Burke, Olivia George
We build off the game, NimG to create a version named Neighboring Nim. By reducing from Geography, we show that this game is PSPACE-hard. The games created by the reduction share s…
Games on the Sperner Triangle
Kyle Burke, Shang-Hua Teng
We create a new two-player game on the Sperner Triangle based on Sperner's lemma. Our game has simple rules and several desirable properties. First, the game is always certain to h…