Kyle's Research

Ongoing Projects

Combinatorial Game Theory Blog.
I maintain a table of Ruleset Properties.
I keep a list of Combinatorial Game Theory meetings including workshops and conferences.

Publications

[DBLP, ORCID, Google Scholar]

The Computational Complexity of Forced-Capture Hnefatafl. K. Burke and Craig Tennenhouse. Theoretical Computer Science vol. 1006 , 27 July 2024. (arXiv) (Summary: A variant of Hnefatafl where players are forced to make capturing moves is PSPACE-hard.)
Nimber-preserving reduction: Game secrets and homomorphic Sprague-Grundy theorem. K. Burke, Matthew Ferland, and Shang-Hua Teng. Theoretical Computer Science vol. 1005 , 24 July 2024. (arXiv) (Summary: We find reductions that preserve not only winnability, but nimber values in impartial games. (Journal version of a paper below.))
A Tractability Gap Beyond Nim-Sums: It’s Hard to Tell Whether a Bunch of Superstars Are Losers. K. Burke, Matthew Ferland, Svenja Huntemann, and Shang-Hua Teng. 12th International Conference on Fun with Algorithms, FUN 2024. LIPICS 291, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2024, ISBN 978-3-95977-314-0: 8:1-14, 29 May 2024. (arXiv) (Summary: Sums of Superstars, games with nimbers as options, are NP-hard.)
Vexing Vexillological Logic. K. Burke and Craig Tennenhouse. International Journal of Game Theory , 24 May 2024. (arXiv) (Summary: The game of Flag Coloring is PSPACE-complete, even on only two colors.)
Nimber-Preserving Reductions: Game Secrets and Homomorphic Sprague-Grundy Theorem. K. Burke, Matthew Ferland, and Shang-Hua Teng. 11th International Conference on Fun with Algorithms, FUN 2022, May 30 to June 3, 2022, Island of Favignana, Sicily, Italy. LIPICS 226, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2022, ISBN 978-3-95977-232-7: 10:1-10:17, 23 May 2022. (arXiv) (Summary: We look at reductions that not only preserve winnability, but also nimbers.)

(13 remaining)

In the Works

Complexity and algorithms for Arc-Kayles and Non-Disconnecting Arc-Kayles. K. Burke, Antoine Dailly, and Nacim Oijid. Submitted. (preprint) (Summary: Non-disconnecting Arc-Kayles is PSPACE-hard)
Keeping Your Distance is Hard. K. Burke, Silvia Heubach, Melissa Huggan, and Svenja Huntemann. To be published in Games of No Chance 6. (preprint) (Summary: Investigates hardness of distance games, finding large families that are PSPACE-complete.)

Presentations

March 18, 2025: Combinatorial Game Theory via Toppling Dominoes, Florida Southern Math Hartje Lecture Series. (Slides - pdf)
Feb. 27, 2025: Algorithmic CGT, Virtual CGT Seminar. (Slides - pdf)
Feb. 25, 2025: Toppling Dominoes, FSC CS Talk. (Slides - pdf)
Feb. 2, 2025: Prove Your Move: A CGT Book for Early Undergraduates, CGTC V. Presented with: Craig Tennenhouse. (Slides - pdf)
Jan. 31, 2025: Triangular-Grid Col is PSPACE-complete, CGTC V. (Slides - pdf)

(46 remaining)