2 citations · 2 across the 12 of their papers we have counts for
Showing 2025Show all
3 papers · 1 filter
cs.CG2025
Undecidability of Tiling with a Tromino
ULB CompGeom Group, Zachary Abel, Hugo Akitaya +6
Given a periodic placement of copies of a tromino (either L or I), we prove co-RE-completeness (and hence undecidability) of deciding whether it can be completed to a plane tiling.…
cs.CC2025
Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete
MIT Hardness Group, Josh Brunner, Lily Chung +4
We prove PSPACE-completeness of Push-1: given a rectangular grid of 1 x 1 cells, each possibly occupied by a movable block, can a robot move from one specified location to another,…
cs.CG2025
All Polyhedral Manifolds are Connected by a 2-Step Refolding
Lily Chung, Erik D. Demaine, Jenny Diomidova +4
We prove that, for any two polyhedral manifolds , there is a polyhedral manifold such that share a common unfolding an…