4 papers
Tetris is Hard with Just One Piece Type
MIT Hardness Group, Josh Brunner, Erik D. Demaine +2
We analyze the computational complexity of Tetris clearing (determining whether the player can clear an initial board using a given sequence of pieces) and survival (determining wh…
Planar Graph Orientation Frameworks, Applied to KPlumber and Polyomino Tiling
MIT Hardness Group, Zachary Abel, Erik D. Demaine +3
Given a graph, when can we orient the edges to satisfy local constraints at the vertices, where each vertex specifies which local orientations of its incident edges are allowed? Th…
Accelerating Blockchain Scalability: New Models for Parallel Transaction Execution in the EVM
Souradeep Das, Konpat Preechakul, Jonas Bäumer +2
As the number of decentralized applications and users on Ethereum grows, the ability of the blockchain to efficiently handle a growing number of transactions becomes increasingly s…
Tetris with Few Piece Types
MIT Hardness Group, Erik D. Demaine, Holden Hall +1
We prove NP-hardness and #P-hardness of Tetris clearing (clearing an initial board using a given sequence of pieces) with the Super Rotation System (SRS), even when the pieces are…