:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	MIT Hardness Group, Abel, Zachary, Demaine, Erik D., Diomidova, Jenny, Li, Jeffery, Zhou, Zixiang
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2603.03488
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Tetris with Few Piece Types
by: MIT Hardness Group, et al.
Published: (2024)

ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
by: MIT Hardness Group, et al.
Published: (2024)

Pushing Blocks without Fixed Walls via Checkable Gizmos: Push-1 is PSPACE-Complete
by: MIT Hardness Group, et al.
Published: (2025)

Complexity of Planar Graph Orientation Consistency, Promise-Inference, and Uniqueness, with Applications to Minesweeper Variants
by: MIT Hardness Group, et al.
Published: (2024)

Tetris is Hard with Just One Piece Type
by: MIT Hardness Group, et al.
Published: (2026)

Walking through Doors is Hard, even without Staircases: Universality and PSPACE-hardness of Planar Door Gadgets
by: MIT Gadgets Group, et al.
Published: (2020)

PSPACE-Hard 2D Super Mario Games: Thirteen Doors
by: MIT Hardness Group, et al.
Published: (2024)

You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games
by: MIT Hardness Group, et al.
Published: (2024)

Complexity of 2D Snake Cube Puzzles
by: MIT Hardness Group, et al.
Published: (2024)

Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude
by: Ani, Hayashi, et al.
Published: (2024)

Undecidability of Tiling with a Tromino
by: ULB CompGeom Group, et al.
Published: (2025)

Graph Threading with Turn Costs
by: Demaine, Erik D., et al.
Published: (2024)

Translational Aperiodic Sets of 7 Polyominoes
by: Yang, Chao, et al.
Published: (2024)

Folding One Polyhedral Metric Graph into Another
by: Chung, Lily, et al.
Published: (2024)

Covering a Polyomino-Shaped Stain with Non-Overlapping Identical Stickers
by: Oka, Keigo, et al.
Published: (2026)

Feedback Set Problems on Bounded-Degree (Planar) Graphs
by: Bai, Tian, et al.
Published: (2026)

Undecidability of Translational Tiling with Three Tiles
by: Yang, Chan, et al.
Published: (2024)

Maximum Reachability Orientation of Mixed Graphs
by: Hörsch, Florian
Published: (2025)

Dynamic Planar Graph Isomorphism is in DynFO
by: Datta, Samir, et al.
Published: (2026)

Multicut Problems in Almost-Planar Graphs: The Dependency of Complexity on the Demand Pattern
by: Hörsch, Florian, et al.
Published: (2025)

Planar Graph Homomorphisms: A Dichotomy and a Barrier from Quantum Groups
by: Cai, Jin-Yi, et al.
Published: (2026)

Tiling with Three Polygons is Undecidable
by: Demaine, Erik D., et al.
Published: (2024)

Geometry Matters in Planar Storyplans
by: Dobler, Alexander, et al.
Published: (2025)

NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles
by: Yang, Chao, et al.
Published: (2024)

Recognizing 2-Layer and Outer $k$-Planar Graphs
by: Kobayashi, Yasuaki, et al.
Published: (2024)

The Parameterized Complexity of Geometric 1-Planarity
by: Firbas, Alexander
Published: (2026)

Linear Planar 3-SAT and Its Applications in Planning
by: Desbois, Victorien, et al.
Published: (2025)

Self-Assembly of Patterns in the abstract Tile Assembly Model
by: Drake, Phillip, et al.
Published: (2024)

Continuous Flattening and Reversing of Convex Polyhedral Linkages
by: Demaine, Erik D., et al.
Published: (2024)

The Parameter Report: An Orientation Guide for Data-Driven Parameterization
by: Komusiewicz, Christian, et al.
Published: (2025)

Intrinsic Universality in Seeded Active Tile Self-Assembly
by: Gomez, Tim, et al.
Published: (2024)

A Polynomial Kernel for Face Cover on Non-Embedded Planar Graphs
by: Hamm, Thekla, et al.
Published: (2026)

Undecidability of Translational Tiling of the 4-dimensional Space with a Set of 4 Polyhypercubes
by: Yang, Chao, et al.
Published: (2024)

Undecidability of Translational Tiling of the 3-dimensional Space with a Set of 6 Polycubes
by: Yang, Chao, et al.
Published: (2024)

Structural Parameters for Steiner Orientation
by: Hanaka, Tesshu, et al.
Published: (2025)

A Linear Kernel for Planar Vector Domination
by: Sahili, Mahabba El, et al.
Published: (2023)

XALP-completeness of Parameterized Problems on Planar Graphs
by: Bodlaender, Hans L., et al.
Published: (2024)

Hexasort -- The Complexity of Stacking Colors on Graphs
by: Klocker, Linus, et al.
Published: (2026)

Push-1 is PSPACE-complete, and the automated verification of motion planning gadgets
by: DeStefano, Zachary, et al.
Published: (2025)

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
by: Eagling-Vose, Tala, et al.
Published: (2025)