Cover Image

Tetris is Hard with Just One Piece Type

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	MIT Hardness Group, Brunner, Josh, Demaine, Erik D., Hendrickson, Della, Li, Jeffery
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
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)

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)

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

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

Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling
by: MIT Hardness Group, et al.
Published: (2026)

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)

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

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

Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification
by: Alman, Josh, et al.
Published: (2025)

The Space Just Above One Clean Qubit
by: Jacobs, Dale, et al.
Published: (2024)

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

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

On the Hardness of Learning One Hidden Layer Neural Networks
by: Li, Shuchen, et al.
Published: (2024)

On the Computational Hardness of Quantum One-Wayness
by: Cavalar, Bruno, et al.
Published: (2023)

Carrying is Hard: Exploring the Gap between Hardness for NP and PSPACE for the Hanano and Jelly no Puzzles
by: Chavrimootoo, Michael C., et al.
Published: (2026)

Hardness of SetCover Reoptimization
by: Jansen, Klaus, et al.
Published: (2025)

On the Hardness of the Drone Delivery Problem
by: Bartlmae, Simon, et al.
Published: (2025)

Improving the Leading Constant of Matrix Multiplication
by: Alman, Josh, et al.
Published: (2024)

Bounds for Hardness Condensation in the Query Model
by: Kayal, Chandrima, et al.
Published: (2026)

Hardness of clique approximation for monotone circuits
by: Błasiok, Jarosław, et al.
Published: (2025)

Hardness Amplification via Group Theory
by: Nareddy, Tejas, et al.
Published: (2024)

Higher Hardness Results for the Reconfiguration of Odd Matchings
by: Dorfer, Joseph
Published: (2026)

Hard-to-Sample Distributions from Robust Extractors
by: Byramji, Farzan, et al.
Published: (2026)

Hard CNF Instances for Ideal Proof Systems
by: Hakoniemi, Tuomas, et al.
Published: (2026)

Are Depth-2 Regular Expressions Hard to Intersect?
by: Ascone, Rocco, et al.
Published: (2025)

Near Optimal Hardness of Approximating $k$-CSP
by: Minzer, Dor, et al.
Published: (2025)

On the Hardness of Order Finding and Equivalence Testing for ROABPs
by: Ramya, C., et al.
Published: (2025)

Hardness Amplification for (Sparse) LPN
by: Aggarwal, Divesh, et al.
Published: (2026)

On the Hardness of Finding Temporally Connected Subgraphs of Any Size
by: Casteigts, Arnaud, et al.
Published: (2026)

New Techniques for Constructing Rare-Case Hard Functions
by: Nareddy, Tejas, et al.
Published: (2024)

Compression of Voxelized Vector Field Data by Boxes is Hard
by: Zhang, Simon
Published: (2025)

Optimal Proof Systems for Complex Sets are Hard to Find
by: Egidy, Fabian, et al.
Published: (2024)

Hardness of Random Reordered Encodings of Parity for Resolution and CDCL
by: Chew, Leroy, et al.
Published: (2024)

Explicit Directional Affine Extractors and Improved Hardness for Linear Branching Programs
by: Li, Xin, et al.
Published: (2023)

Worst-Case and Average-Case Hardness of Hypercycle and Database Problems
by: Fu, Cheng-Hao, et al.
Published: (2025)

On the NP-Hardness Approximation Curve for Max-2Lin(2)
by: Martinsson, Björn
Published: (2024)

PCP-free APX-Hardness of Nearest Codeword and Minimum Distance
by: Bhattiprolu, Vijay, et al.
Published: (2025)

Hardness of Hypergraph Edge Modification Problems
by: Gishboliner, Lior, et al.
Published: (2025)