Isaac Grosof

Vassar College, Carnegie Mellon University

Papers

Total Citations

H-Index

About

Isaac Grosof is a researcher whose work lies at the intersection of computational geometry, motion planning, and recreational complexity theory. His research primarily explores the fundamental computational limits of robotic and puzzle-based movement, with a focus on classifying the difficulty of navigating through stateful environments. Grosof’s most notable contribution is his seminal 2018 paper, *"Computational Complexity of Motion Planning of a Robot through Simple Gadgets,"* which has garnered 12 citations and establishes a general framework for analyzing motion planning through graphs of interactive "gadgets"—a setup common to many robotic systems. This work provides a powerful lens for understanding how a robot’s path can be complicated by objects that change state upon traversal. Additionally, his 2017 paper, *"Push-Pull Block Puzzles are Hard,"* settles an open question by proving that 3D push-pull puzzles are PSPACE-complete and 2D variants with thin walls are NP-hard, bridging the gap between recreational puzzles and serious computational theory. Through these contributions, Grosof has illuminated the deep complexity underlying seemingly simple movement tasks, making his research essential reading for anyone interested in the theoretical foundations of robotics and algorithmic puzzle-solving.