5 citations · 28 across the 19 of their papers we have counts for
3 papers · 1 filter
Fine-Grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy
Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu +2
This paper initiates the study of I/O algorithms (minimizing cache misses) from the perspective of fine-grained complexity (conditional polynomial lower bounds). Specifically, we a…
Push-Pull Block Puzzles are Hard
Erik D. Demaine, Isaac Grosof, Jayson Lynch
This paper proves that push-pull block puzzles in 3D are PSPACE-complete to solve, and push-pull block puzzles in 2D with thin walls are NP-hard to solve, settling an open question…
Minimal forcing sets for 1D origami
Mirela Damian, Erik Demaine, Muriel Dulieu +5
This paper addresses the problem of finding minimum forcing sets in origami. The origami material folds flat along straight lines called creases that can be labeled as mountains or…