5 citations · 6 across the 4 of their papers we have counts for
7 papers
Data Races and the Discrete Resource-time Tradeoff Problem with Resource Reuse over Paths
Rathish Das, Shih-Yu Tsai, Sharmila Duppala +5
A determinacy race occurs if two or more logically parallel instructions access the same memory location and at least one of them tries to modify its content. Races often lead to n…
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…
Toward an Energy Efficient Language and Compiler for (Partially) Reversible Algorithms
Nirvan Tyagi, Jayson Lynch, Erik D. Demaine
We introduce a new programming language for expressing reversibility, Energy-Efficient Language (Eel), geared toward algorithm design and implementation. Eel is the first language…
Energy-Efficient Algorithms
Erik D. Demaine, Jayson Lynch, Geronimo J. Mirano +1
We initiate the systematic study of the energy complexity of algorithms (in addition to time and space complexity) based on Landauer's Principle in physics, which gives a lower bou…