Quicklists
Javascript must be enabled

Alan Guo : Lattice point methods for combinatorial games

We encode arbitrary finite impartial combinatorial games in terms of lattice points in rational convex polyhedra. Encodings provided by these lattice games can be made particularly efficient for octal games, which we generalize to squarefree games. These encompass all heap games in a natural setting where the Sprague-Grundy theorem for normal play manifests itself geometrically. We provide polynomial-time algorithms for computing strategies for lattice games provided that they have a certain algebraic structure, called an affine stratification.

Add to Favorites

Please select playlist name from following

Create new playlist

Report Video

Please select the category that most closely reflects your concern about the video, so that we can review it and determine whether it violates our Community Guidelines or isn’t appropriate for all viewers. Abusing this feature is also a violation of the Community Guidelines, so don’t do it.

0 Comments

Comments Disabled For This Video