Showing 2026Show all
2 papers · 1 filter
cs.CC2026
Tetris is Hard with Just One Piece Type
MIT Hardness Group, Josh Brunner, Erik D. Demaine +2
We analyze the computational complexity of Tetris clearing (determining whether the player can clear an initial board using a given sequence of pieces) and survival (determining wh…
cs.CC2026
Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling
MIT Hardness Group, Zachary Abel, Erik D. Demaine +3
Given a graph, when can we orient the edges to satisfy local constraints at the vertices, where each vertex specifies which local orientations of its incident edges are allowed? Th…