Adventures in Maze Folding Art by Demaine, Erik D, Demaine, Martin L

“…© 2020 Information Processing Society of Japan. Every orthogonal graph, extruded orthogonally from a rectangle, can be folded from a rectangle of paper a constant factor larger. …”
Get full text

PSPACE-completeness of Pulling Blocks to Reach a Goal by Ani, Joshua, Asif, Sualeh, Demaine, Erik D, Diomidov, Yevhenii, Hendrickson, Dylan, Lynch, Jayson, Scheffler, Sarah, Suhl, Adam

“…© 2020 Information Processing Society of Japan. We prove PSPACE-completeness of all but one problem in a large space of pulling-block problems where the goal is for the agent to reach a target destination. …”
Get full text

Total Tetris: Tetris with Monominoes, Dominoes, Trominoes, Pentominoes,... by Demaine, Erik D, Demaine, Martin L, Eisenstat, Sarah Charmian, Hesterberg, Adam Classen, Lincoln, Andrea I, Lynch, Jayson R.

Get full text

Folding and Punching Paper by Asao, Yasuhiko, Demaine, Erik D, Demaine, Martin L, Hosaka, Hideaki, Kawamura, Akitoshi, Tachi, Tomohiro, Takahashi, Kazune

Get full text

Tetris is NP-hard even with O (1) Rows or Columns by Asif, Sualeh, Coulombe, Michael, Demaine, Erik D, Demaine, Martin L, Hesterberg, Adam, Lynch, Jayson, Singhal, Mihir

“…© 2020 Information Processing Society of Japan. We prove that the classic falling-block video game Tetris (both survival and board clearing) remains NP-complete even when restricted to 8 columns, or to 4 rows, settling open problems posed over 15 years ago. …”
Get full text

Understanding attack trends from security blog posts using guided-topic model by Nagai, Tatsuya, Takita, Makoto, Furumoto, Keisuke, Shiraishi, Yoshiaki, Xia, Kelin, Takano, Yasuhiro, Mohri, Masami, Morii, Masakatu

Get full text

Even 1 × n Edge-Matching and Jigsaw Puzzles are Really Hard by Bosboom, Jeffrey William, Demaine, Erik D, Demaine, Martin L, Hesterberg, Adam Classen, Manurangsi, Pasin, Yodpinyanee, Anak

Get full text

Edge Matching with Inequalities, Triangles, Unknown Shape, and Two Players by Bosboom, Jeffrey, Chen, Charlotte, Chung, Lily, Compton, Spencer, Coulombe, Michael, Demaine, Erik D, Demaine, Martin L, Filho, Ivan Tadeu Ferreira Antunes, Hendrickson, Dylan, Hesterberg, Adam, Hsu, Calvin, Hu, William, Korten, Oliver, Luo, Zhezheng, Zhang, Lillian

“…© 2020 Information Processing Society of Japan. We analyze the computational complexity of several new variants of edge-matching puzzles. …”
Get full text

Folded Structures Satisfying Multiple Conditions by Demaine, Erik D, Ku, Jason S

Get full text

An efficient anonymous reputation system for crowdsensing by Shahidatul Sadiah, Shahidatul Sadiah, Nakanishi, Toru

Get full text

Zig-Zag Numberlink is NP-Complete by Adcock, Aaron, Reidl, Felix, Demaine, Erik D., Demaine, Martin L., O'Brien, Michael P., Villaamil, Fernando Sanchez, Sullivan, Blair D.

Get full text
Get full text

An efficient anonymous reputation system for crowd sensing by Shahidatul Sadiah, Shahidatul Sadiah, Nakanishi, Toru

Finding a Hamiltonian Path in a Cube with Specified Turns is Hard by Abel, Zachary Ryan, Demaine, Erik D., Demaine, Martin L., Eisenstat, Sarah Charmian, Lynch, Jayson R., Schardl, Tao Benjamin

Get full text
Get full text
Get full text
Get full text
Get full text