Papers
9
Total Citations
38
H-Index
4
About
Jayson Lynch is a theoretical computer scientist whose research centers on computational complexity, motion planning, and combinatorial puzzle theory. He is best known for pioneering a general framework for analyzing the complexity of robot motion planning through networks of stateful "gadgets" — abstract components whose internal states govern how a robot may traverse them. This foundational work, introduced in 2018 and expanded through 2020, has become a unifying lens for understanding why so many motion planning problems and video games are computationally hard, earning his most-cited paper 12 citations and spawning a productive line of follow-up research. Beyond this theoretical framework, Lynch has proven hardness results for concrete problems including push-pull block puzzles — establishing PSPACE-completeness in 3D and NP-hardness in 2D — and demonstrated the hardness of token swapping on trees, a combinatorial problem with broad algorithmic relevance. His work on modular pivoting robots further bridges theory and robotics, delivering both hardness proofs and efficient reconfiguration algorithms for hexagonal grid modules. Across his body of work, Lynch exemplifies rigorous complexity-theoretic reasoning applied to motion, reconfiguration, and recreational mathematics, making his research valuable to students in algorithms, robotics, and combinatorial game theory.
Research Focus
Key Achievements
Top Papers
- 1
- 2Push-Pull Block Puzzles are Hard5 citations · 2017
- 3
- 4Hardness of Token Swapping on Trees4 citations · 2021
- 5
- 6
- 7Characterizing Universal Reconfigurability of Modular Pivoting Robots2 citations · 2021
- 8Push-Pull Block Puzzles are Hard2 citations · 2017
- 9Characterizing Universal Reconfigurability of Modular Pivoting Robots2 citations · 2020