Erik D. Demaine
Publication record assembled from the DBLP archive of ranked conferences.
Papers indexed
204
Venues
47
Active years
1998–2026
Best venue rank
A*
Where they publish
- A*SODA28 papers
- NationalFUN24 papers
- BISAAC23 papers
- BWADS21 papers
- AESA14 papers
- A*ICALP11 papers
- BDNA7 papers
- AGD6 papers
- ASTACS6 papers
- BLATIN6 papers
- BSPAA5 papers
- BWALCOM4 papers
- A*STOC4 papers
- A*FOCS4 papers
- NationalCOCOON3 papers
- A*ICRA3 papers
- BMFCS3 papers
- CAlgosensors2 papers
- AALENEX2 papers
- CIWOCA1 paper
- A*LICS1 paper
- CUC1 paper
- CMCU1 paper
- A*AAAI1 paper
- A*ICML1 paper
- NationalCSR1 paper
- CCIAC1 paper
- CRC1 paper
- CICPRAM1 paper
- A*WWW1 paper
- CSPIRE1 paper
- CTAMC1 paper
- CCOCOA1 paper
- A*POPL1 paper
- CWAW1 paper
- BWG1 paper
- AIROS1 paper
- CWAFR1 paper
- A*PODC1 paper
- A*INFOCOM1 paper
- BMOBIHOC1 paper
- A*SOSP1 paper
- A*SIGGRAPH1 paper
- BSSDBM1 paper
- AIMC1 paper
- UnrankedSENSYS1 paper
- CWABI1 paper
Papers
204 indexed papers, newest first.
| Year | Venue | Title | Authors |
|---|---|---|---|
| 2026 | FUN | A Bookworm Climbs up the Polynomial Hierarchy: Meta-Restoration Complexity in Arithmetic Puzzles. | Brynmor Chapman, Lily Chung, Erik D. Demaine, Yota Irino, Della H. Hendrickson, Tonan Kamata, Ryuhei Uehara |
| 2026 | FUN | Tetris Is Hard with Just One Piece Type. | MIT Hardness Group, Josh Brunner, Erik D. Demaine, Della H. Hendrickson, Jeffery Li |
| 2025 | GD | The Price of Connectivity Augmentation on Planar Graphs. | Hugo A. Akitaya, Justin Dallant, Erik D. Demaine, Michael Kaufmann, Linda Kleist, Frederick Stock, Csaba D. Tth, Torsten Ueckerdt |
| 2025 | IWOCA | ETH Lower Bounds for n-Queens: Time Waits for Nobody. | Josh Brunner, Erik D. Demaine, Timothy Gomez, Markus Hecher, Meryl Zhang |
| 2025 | LICS | #P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought? | Max Bannach, Erik D. Demaine, Timothy Gomez, Markus Hecher |
| 2024 | DNA | Domain-Based Nucleic-Acid Minimum Free Energy: Algorithmic Hardness and Parameterized Bounds. | Erik D. Demaine, Timothy Gomez, Elise Grizzell, Markus Hecher, Jayson Lynch, Robert Schweller, Ahmed Shalaby, Damien Woods |
| 2024 | FUN | PSPACE-Hard 2D Super Mario Games: Thirteen Doors. | MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, Matias Korman |
| 2024 | FUN | You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games. | MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, Ricardo Ruiz, Naveen Venkat |
| 2024 | FUN | ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles. | MIT Hardness Group, Josh Brunner, Lily Chung, Erik D. Demaine, Della H. Hendrickson, Andy Tockman |
| 2024 | FUN | Tetris with Few Piece Types. | MIT Hardness Group, Erik D. Demaine, Holden Hall, Jeffery Li |
| 2024 | ISAAC | Minimum Plane Bichromatic Spanning Trees. | Hugo A. Akitaya, Ahmad Biniaz, Erik D. Demaine, Linda Kleist, Frederick Stock, Csaba D. Tth |
| 2024 | ISAAC | Easier Ways to Prove Counting Hard: A Dichotomy for Generalized #SAT, Applied to Constraint Graphs. | MIT Hardness Group, Josh Brunner, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Markus Hecher, Frederick Stock, Zixiang Zhou |
| 2024 | UC | Agent Motion Planning as Block Asynchronous Cellular Automata: Pushing, Pulling, Suplexing, and More. | Hayashi Ani, Josh Brunner, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Della H. Hendrickson, Yael Kirkpatrick, Jeffery Li, Jayson Lynch, Ritam Nag, Frederick Stock |
| 2023 | DNA | Complexity of Reconfiguration in Surface Chemical Reaction Networks. | Robert M. Alaniz, Josh Brunner, Michael J. Coulombe, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Elise Grizzell, Ryan Knobel, Jayson Lynch, Andrew Rodriguez, Robert Schweller, Tim Wylie |
| 2022 | ESA | Hardness of Token Swapping on Trees. | Oswin Aichholzer, Erik D. Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masrov, Mikhail Rudoy, Virginia Vassilevska Williams, Nicole Wein |
| 2022 | FUN | Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude. | Joshua Ani, Lily Chung, Erik D. Demaine, Jenny Diomidova, Dylan H. Hendrickson, Jayson Lynch |
| 2022 | FUN | Rolling Polyhedra on Tessellations. | Akira Baes, Erik D. Demaine, Martin L. Demaine, Elizabeth J. Hartung, Stefan Langerman, Joseph O'Rourke, Ryuhei Uehara, Yushi Uno, Aaron Williams |
| 2022 | ISAAC | Lower Bounds on Retroactive Data Structures. | Lily Chung, Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch |
| 2022 | MCU | PSPACE-Completeness of Reversible Deterministic Systems. | Erik D. Demaine, Robert A. Hearn, Dylan H. Hendrickson, Jayson Lynch |
| 2022 | WALCOM | Traversability, Reconfiguration, and Reachability in the Gadget Framework. | Joshua Ani, Erik D. Demaine, Jenny Diomidova, Dylan H. Hendrickson, Jayson Lynch |
| 2022 | WALCOM | Trains, Games, and Complexity: 0/1/2-Player Motion Planning Through Input/Output Gadgets. | Joshua Ani, Erik D. Demaine, Dylan H. Hendrickson, Jayson Lynch |
| 2021 | AAAI | Scalable Equilibrium Computation in Multi-agent Influence Games on Networks. | Fotini Christia, Michael J. Curry, Constantinos Daskalakis, Erik D. Demaine, John P. Dickerson, MohammadTaghi Hajiaghayi, Adam Hesterberg, Marina Knittel, Aidan Milliff |
| 2021 | FUN | Tatamibari Is NP-Complete. | Aviv Adler, Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Quanquan C. Liu, Jayson Lynch |
| 2021 | FUN | Walking Through Doors Is Hard, Even Without Staircases: Proving PSPACE-Hardness via Planar Assemblies of Door Gadgets. | Joshua Ani, Jeffrey Bosboom, Erik D. Demaine, Jenny Diomidova, Dylan H. Hendrickson, Jayson Lynch |
| 2021 | FUN | 1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete. | Josh Brunner, Lily Chung, Erik D. Demaine, Dylan H. Hendrickson, Adam Hesterberg, Adam Suhl, Avi Zeff |
| 2021 | ICML | Multidimensional Scaling: Approximation and Complexity. | Erik D. Demaine, Adam Hesterberg, Frederic Koehler, Jayson Lynch, John Urschel |
| 2020 | ISAAC | Arithmetic Expression Construction. | Leo Alcock, Sualeh Asif, Jeffrey Bosboom, Josh Brunner, Charlotte Chen, Erik D. Demaine, Rogers Epstein, Adam Hesterberg, Lior Hirschfeld, William Hu, Jayson Lynch, Sarah Scheffler, Lillian Zhang |
| 2020 | ISAAC | Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard. | Josh Brunner, Erik D. Demaine, Dylan H. Hendrickson, Julian Wellman |
| 2020 | ISAAC | Recursed Is Not Recursive: A Jarring Result. | Erik D. Demaine, Justin Kopinsky, Jayson Lynch |
| 2019 | CSR | Belga B-Trees. | Erik D. Demaine, John Iacono, Grigorios Koumoutsos, Stefan Langerman |
| 2019 | DNA | Simulation of Programmable Matter Systems Using Active Tile-Based Self-Assembly. | John Calvin Alumbaugh, Joshua J. Daymude, Erik D. Demaine, Matthew J. Patitz, Andra W. Richa |
| 2019 | ESA | Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers. | Hugo A. Akitaya, Esther M. Arkin, Mirela Damian, Erik D. Demaine, Vida Dujmovic, Robin Y. Flatland, Matias Korman, Beln Palop, Irene Parada, Andr van Renssen, Vera Sacristn |
| 2019 | ESA | Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class. | Erik D. Demaine, Timothy D. Goodrich, Kyle Kloster, Brian Lavallee, Quanquan C. Liu, Blair D. Sullivan, Ali Vakilian, Andrew van der Poel |
| 2019 | WADS | Reconfiguring Undirected Paths. | Erik D. Demaine, David Eppstein, Adam Hesterberg, Kshitij Jain, Anna Lubiw, Ryuhei Uehara, Yushi Uno |
| 2018 | COCOON | Reconfiguration of Satisfying Assignments and Subset Sums: Easy to Find, Hard to Connect. | Jean Cardinal, Erik D. Demaine, David Eppstein, Robert A. Hearn, Andrew Winslow |
| 2018 | DNA | Know When to Fold 'Em: Self-assembly of Shapes by Folding in Oritatami. | Erik D. Demaine, Jacob Hendricks, Meagan Olsen, Matthew J. Patitz, Trent A. Rogers, Nicolas Schabanel, Shinnosuke Seki, Hadley Thomas |
| 2018 | FUN | Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible. | Zachary Abel, Jeffrey Bosboom, Erik D. Demaine, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch, Mikhail Rudoy |
| 2018 | FUN | Computational Complexity of Generalized Push Fight. | Jeffrey Bosboom, Erik D. Demaine, Mikhail Rudoy |
| 2018 | FUN | Computational Complexity of Motion Planning of a Robot through Simple Gadgets. | Erik D. Demaine, Isaac Grosof, Jayson Lynch, Mikhail Rudoy |
| 2018 | FUN | The Computational Complexity of Portal and Other 3D Video Games. | Erik D. Demaine, Joshua Lockhart, Jayson Lynch |
| 2018 | STACS | Solving the Rubik's Cube Optimally is NP-complete. | Erik D. Demaine, Sarah Eisenstat, Mikhail Rudoy |
| 2018 | SPAA | Red-Blue Pebble Game: Complexity of Computing the Trade-Off between Cache Size and Memory Transfers. | Erik D. Demaine, Quanquan C. Liu |
| 2017 | CIAC | Push-Pull Block Puzzles are Hard. | Erik D. Demaine, Isaac Grosof, Jayson Lynch |
| 2017 | GD | Upward Partitioned Book Embeddings. | Hugo A. Akitaya, Erik D. Demaine, Adam Hesterberg, Quanquan C. Liu |
| 2017 | SODA | Three Colors Suffice: Conflict-Free Coloring of Planar Graphs. | Zachary Abel, Victor Alvarez, Erik D. Demaine, Sndor P. Fekete, Aman Gour, Adam Hesterberg, Phillip Keldenich, Christian Scheffer |
| 2017 | SODA | Universal Shape Replicators via Self-Assembly with Attractive and Repulsive Forces. | Cameron T. Chalk, Erik D. Demaine, Martin L. Demaine, Eric Martinez, Robert Schweller, Luis Vega, Tim Wylie |
| 2017 | WADS | Universal Hinge Patterns for Folding Strips Efficiently into Any Grid Polyhedron. | Nadia M. Benbernou, Erik D. Demaine, Martin L. Demaine, Anna Lubiw |
| 2017 | WADS | Inapproximability of the Standard Pebble Game and Hard to Pebble Graphs. | Erik D. Demaine, Quanquan C. Liu |
| 2017 | WALCOM | Sequentially Swapping Colored Tokens on Graphs. | Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-Ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno |
| 2016 | FUN | The Fewest Clues Problem. | Erik D. Demaine, Fermi Ma, Ariel Schvartzman, Erik Waingarten, Scott Aaronson |
| 2016 | FUN | Super Mario Bros. is Harder/Easier Than We Thought. | Erik D. Demaine, Giovanni Viglietta, Aaron Williams |
| 2016 | ICALP | The Complexity of Hex and the Jordan Curve Theorem. | Aviv Adler, Constantinos Daskalakis, Erik D. Demaine |
| 2016 | RC | Toward an Energy Efficient Language and Compiler for (Partially) Reversible Algorithms. | Nirvan Tyagi, Jayson Lynch, Erik D. Demaine |
| 2016 | STOC | A PTAS for planar group Steiner tree via spanner bootstrapping and prize collecting. | MohammadHossein Bateni, Erik D. Demaine, MohammadTaghi Hajiaghayi, Dniel Marx |
| 2016 | SPAA | Cache-Adaptive Analysis. | Michael A. Bender, Erik D. Demaine, Roozbeh Ebrahimi, Jeremy T. Fineman, Rob Johnson, Andrea Lincoln, Jayson Lynch, Samuel McCauley |
| 2015 | DNA | New Geometric Algorithms for Fully Connected Staged Self-Assembly. | Erik D. Demaine, Sndor P. Fekete, Christian Scheffer, Arne Schmidt |
| 2015 | ICPRAM | A Dissimilarity Measure for Comparing Origami Crease Patterns. | Seung Man Oh, Godfried T. Toussaint, Erik D. Demaine, Martin L. Demaine |
| 2015 | ICRA | Particle computation: Device fan-out and binary memory. | Hamed Mohtasham Shad, Rose Morris-Wright, Erik D. Demaine, Sndor P. Fekete, Aaron T. Becker |
| 2015 | WADS | Cache-Oblivious Iterated Predecessor Queries via Range Coalescing. | Erik D. Demaine, Vineet Gopal, William Hasenplaugh |
| 2015 | WADS | Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing. | Erik D. Demaine, Tim Kaler, Quanquan C. Liu, Aaron Sidford, Adam Yedidia |
| 2015 | WALCOM | Folding a Paper Strip to Minimize Thickness. | Erik D. Demaine, David Eppstein, Adam Hesterberg, Hiro Ito, Anna Lubiw, Ryuhei Uehara, Yushi Uno |
| 2014 | FUN | Classic Nintendo Games Are (Computationally) Hard. | Greg Aloupis, Erik D. Demaine, Alan Guo, Giovanni Viglietta |
| 2014 | FUN | Fun with Fonts: Algorithmic Typography. | Erik D. Demaine, Martin L. Demaine |
| 2014 | FUN | Playing Dominoes Is Hard, Except by Yourself. | Erik D. Demaine, Fermi Ma, Erik Waingarten |
| 2014 | FUN | Swapping Labeled Tokens on Graphs. | Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, Takeaki Uno |
| 2014 | GD | Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths. | Zachary Abel, Erik D. Demaine, Martin L. Demaine, David Eppstein, Anna Lubiw, Ryuhei Uehara |
| 2014 | ICALP | One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile. | Erik D. Demaine, Martin L. Demaine, Sndor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, Damien Woods |
| 2014 | ICALP | Canadians Should Travel Randomly. | Erik D. Demaine, Yamming Huang, Chung-Shou Liao, Kunihiko Sadakane |
| 2014 | ICRA | An end-to-end approach to making self-folded 3D surface shapes by uniform heating. | Byoungkwon An, Shuhei Miyashita, Michael Thomas Tolley, Daniel M. Aukes, Laura Meeker, Erik D. Demaine, Martin L. Demaine, Robert J. Wood, Daniela Rus |
| 2014 | ICRA | Particle computation: Designing worlds to control robot swarms with only global signals. | Aaron T. Becker, Erik D. Demaine, Sndor P. Fekete, James McLurkin |
| 2014 | ISAAC | Polynomial-Time Algorithm for Sliding Tokens on Trees. | Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, Takeshi Yamada |
| 2014 | WWW | How to influence people with partial incentives. | Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, David L. Malec, S. Raghavan, Anshul Sawant, Morteza Zadimoghaddam |
| 2013 | Algosensors | Reconfiguring Massive Particle Swarms with Limited, Global Control. | Aaron T. Becker, Erik D. Demaine, Sndor P. Fekete, Golnaz Habibi, James McLurkin |
| 2013 | ICALP | Combining Binary Search Trees. | Erik D. Demaine, John Iacono, Stefan Langerman, zgr zkan |
| 2013 | ICALP | The Two-Handed Tile Assembly Model Is Not Intrinsically Universal. | Erik D. Demaine, Matthew J. Patitz, Trent A. Rogers, Robert T. Schweller, Scott M. Summers, Damien Woods |
| 2013 | SODA | Learning Disjunctions: Near-Optimal Trade-off between Mistakes and "I Don't Know's". | Erik D. Demaine, Morteza Zadimoghaddam |
| 2013 | STACS | Algorithms for Designing Pop-Up Cards. | Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, Andr Schulz, Diane L. Souvaine, Giovanni Viglietta, Andrew Winslow |
| 2013 | STACS | Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM. | Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers, Andrew Winslow |
| 2013 | WADS | Blame Trees. | Erik D. Demaine, Pavel Panchekha, David A. Wilson, Edward Z. Yang |
| 2012 | FUN | Picture-Hanging Puzzles. | Erik D. Demaine, Martin L. Demaine, Yair N. Minsky, Joseph S. B. Mitchell, Ronald L. Rivest, Mihai Patrascu |
| 2012 | ISAAC | Origami Robots and Star Trek Replicators. | Erik D. Demaine |
| 2011 | DNA | One-Dimensional Staged Self-assembly. | Erik D. Demaine, Sarah Eisenstat, Mashhood Ishaque, Andrew Winslow |
| 2011 | ESA | Algorithms for Solving Rubik's Cubes. | Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, Andrew Winslow |
| 2011 | ISAAC | Folding Equilateral Plane Graphs. | Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, Tao B. Schardl, Isaac Shapiro-Ellowitz |
| 2011 | SODA | Embedding Stacked Polytopes on a Polynomial-Size Grid. | Erik D. Demaine, Andr Schulz |
| 2011 | STOC | Contraction decomposition in h-minor-free graphs and algorithmic applications. | Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi |
| 2011 | STACS | Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (extended abstract). | Erik D. Demaine, Matthew J. Patitz, Robert T. Schweller, Scott M. Summers |
| 2011 | SPIRE | Constructing Strings at the Nano Scale via Staged Self-assembly. | Erik D. Demaine |
| 2011 | TAMC | Approximability of the Subset Sum Reconfiguration Problem. | Takehiro Ito, Erik D. Demaine |
| 2011 | WADS | Lossless Fault-Tolerant Data Structures with Additive Overhead. | Paul F. Christiano, Erik D. Demaine, Shaunak Kishore |
| 2011 | WADS | Flattening Fixed-Angle Chains Is Strongly NP-Hard. | Erik D. Demaine, Sarah Eisenstat |
| 2010 | COCOA | Coverage with | Brad Ballinger, Nadia M. Benbernou, Prosenjit Bose, Mirela Damian, Erik D. Demaine, Vida Dujmovic, Robin Y. Flatland, Ferran Hurtado, John Iacono, Anna Lubiw, Pat Morin, Vera Sacristn Adinolfi, Diane L. Souvaine, Ryuhei Uehara |
| 2010 | FUN | Kaboozle Is NP-complete, Even in a Strip. | Tetsuo Asano, Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara |
| 2010 | FUN | UNO Is Hard, Even for a Single Player. | Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara, Takeaki Uno, Yushi Uno |
| 2010 | LATIN | Matching Points with Things. | Greg Aloupis, Jean Cardinal, Sbastien Collette, Erik D. Demaine, Martin L. Demaine, Muriel Dulieu, Ruy Fabila-Monroy, Vi Hart, Ferran Hurtado, Stefan Langerman, Maria Saumell, Carlos Seara, Perouz Taslakian |
| 2010 | POPL | Reconfigurable asynchronous logic automata: (RALA). | Neil Gershenfeld, David Dalrymple, Kailiang Chen, Ara N. Knaian, Forrest Green, Erik D. Demaine, Scott Greenwald, Peter Schmidt-Nielsen |
| 2010 | SODA | Shape Replication through Self-Assembly and RNase Enzymes. | Zachary Abel, Nadia M. Benbernou, Mirela Damian, Erik D. Demaine, Martin L. Demaine, Robin Y. Flatland, Scott Duke Kominers, Robert Schweller |
| 2010 | SODA | Cache-Oblivious Dynamic Dictionaries with Update/Query Tradeoffs. | Gerth Stlting Brodal, Erik D. Demaine, Jeremy T. Fineman, John Iacono, Stefan Langerman, J. Ian Munro |
| 2010 | SODA | Decomposition, Approximation, and Coloring of Odd-Minor-Free Graphs. | Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi |
| 2010 | SPAA | Basic network creation games. | Noga Alon, Erik D. Demaine, MohammadTaghi Hajiaghayi, Tom Leighton |
| 2010 | SPAA | Scheduling to minimize power consumption using submodular functions. | Erik D. Demaine, Morteza Zadimoghaddam |
| 2010 | WAW | Constant Price of Anarchy in Network Creation Games via Public Service Advertising. | Erik D. Demaine, Morteza Zadimoghaddam |
| 2010 | WG | Algorithmic Graph Minors and Bidimensionality. | Erik D. Demaine |
| 2009 | Algosensors | Invited Talk I Actuator Nets: Folding, Reconfiguring and Deploying Sensors. | Erik D. Demaine |
| 2009 | ESA | Algorithms Meet Art, Puzzles, and Magic. | Erik D. Demaine |
| 2009 | ESA | Minimizing Movement: Fixed-Parameter Tractability. | Erik D. Demaine, MohammadTaghi Hajiaghayi, Dniel Marx |
| 2009 | ICALP | Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs. | Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi |
| 2009 | ICALP | Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs. | Erik D. Demaine, MohammadTaghi Hajiaghayi, Philip N. Klein |
| 2009 | ICALP | On Cartesian Trees and Range Minimum Queries. | Erik D. Demaine, Gad M. Landau, Oren Weimann |
| 2009 | IROS | A Distributed boundary detection algorithm for multi-robot systems. | James McLurkin, Erik D. Demaine |
| 2009 | ISAAC | Algorithmic Folding Complexity. | Jean Cardinal, Erik D. Demaine, Martin L. Demaine, Shinji Imahori, Stefan Langerman, Ryuhei Uehara |
| 2009 | ISAAC | Folding a Better Checkerboard. | Erik D. Demaine, Martin L. Demaine, Goran Konjevod, Robert J. Lang |
| 2009 | SODA | The geometry of binary search trees. | Erik D. Demaine, Dion Harmon, John Iacono, Daniel Kane, Mihai Patrascu |
| 2009 | SODA | Additive approximation algorithms for list-coloring minor-closed class of graphs. | Ken-ichi Kawarabayashi, Erik D. Demaine, MohammadTaghi Hajiaghayi |
| 2009 | STACS | Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs. | Glencora Borradaile, Erik D. Demaine, Siamak Tazari |
| 2009 | STACS | The Price of Anarchy in Cooperative Network Creation Games. | Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, Morteza Zadimoghaddam |
| 2009 | WADS | Minimal Locked Trees. | Brad Ballinger, David Charlton, Erik D. Demaine, Martin L. Demaine, John Iacono, Ching-Hao Liu, Sheung-Hung Poon |
| 2009 | WADS | Algorithms Meet Art, Puzzles, and Magic. | Erik D. Demaine |
| 2009 | WADS | Reconfiguration of List Edge-Colorings in a Graph. | Takehiro Ito, Marcin Kaminski, Erik D. Demaine |
| 2009 | WADS | A Pseudopolynomial Algorithm for Alexandrov's Theorem. | Daniel Kane, Gregory N. Price, Erik D. Demaine |
| 2008 | ISAAC | Reconfiguration of Cube-Style Modular Robots Using O(logn) Parallel Moves. | Greg Aloupis, Sbastien Collette, Erik D. Demaine, Stefan Langerman, Vera Sacristn Adinolfi, Stefanie Wuhrer |
| 2008 | ISAAC | On the Complexity of Reconfiguration Problems. | Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno |
| 2008 | WAFR | Realistic Reconfiguration of Crystalline (and Telecube) Robots. | Greg Aloupis, Sbastien Collette, Mirela Damian, Erik D. Demaine, Dania El-Khechen, Robin Y. Flatland, Stefan Langerman, Joseph O'Rourke, Val Pinciu, Suneeta Ramaswami, Vera Sacristn Adinolfi, Stefanie Wuhrer |
| 2007 | DNA | Staged Self-assembly: Nanomanufacture of Arbitrary Shapes with | Erik D. Demaine, Martin L. Demaine, Sndor P. Fekete, Mashhood Ishaque, Eynat Rafalin, Robert T. Schweller, Diane L. Souvaine |
| 2007 | ICALP | An Optimal Decomposition Algorithm for Tree Edit Distance. | Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann |
| 2007 | ISAAC | Linear Reconfiguration of Cube-Style Modular Robots. | Greg Aloupis, Sbastien Collette, Mirela Damian, Erik D. Demaine, Robin Y. Flatland, Stefan Langerman, Joseph O'Rourke, Suneeta Ramaswami, Vera Sacristn Adinolfi, Stefanie Wuhrer |
| 2007 | PODC | The price of anarchy in network creation games. | Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, Morteza Zadimoghaddam |
| 2007 | SODA | Approximation algorithms via contraction decomposition. | Erik D. Demaine, Mohammad Taghi Hajiaghayi, Bojan Mohar |
| 2007 | SODA | Minimizing movement. | Erik D. Demaine, Mohammad Taghi Hajiaghayi, Hamid Mahini, Amin S. Sayedi-Roshkhar, Shayan Oveis Gharan, Morteza Zadimoghaddam |
| 2007 | SPAA | Scheduling to minimize gaps and power consumption. | Erik D. Demaine, Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, Amin S. Sayedi-Roshkhar, Morteza Zadimoghaddam |
| 2007 | WADS | The Stackelberg Minimum Spanning Tree Game. | Jean Cardinal, Erik D. Demaine, Samuel Fiorini, Gwenal Joret, Stefan Langerman, Ilan Newman, Oren Weimann |
| 2007 | WADS | A Pseudopolynomial Time | Ajay Deshpande, Taejung Kim, Erik D. Demaine, Sanjay E. Sarma |
| 2006 | ESA | Necklaces, Convolutions, and | David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Perouz Taslakian |
| 2006 | ESA | Origami, Linkages, and Polyhedra: Folding with Algorithms. | Erik D. Demaine |
| 2006 | ISAAC | Algorithmic Graph Minor Theory: Improved Grid Minor Bounds and Wagner's Contraction. | Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi |
| 2006 | ISAAC | Approximability of Partitioning Graphs with Supply and Demand. | Takehiro Ito, Erik D. Demaine, Xiao Zhou, Takao Nishizeki |
| 2006 | LATIN | Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams. | Boris Aronov, Prosenjit Bose, Erik D. Demaine, Joachim Gudmundsson, John Iacono, Stefan Langerman, Michiel H. M. Smid |
| 2006 | LATIN | Optimally Adaptive Integration of Univariate Lipschitz Functions. | Ilya Baran, Erik D. Demaine, Dmitriy A. Katz |
| 2006 | LATIN | De Dictionariis Dynamicis Pauco Spatio Utentibus ( | Erik D. Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, Mihai Patrascu |
| 2006 | SODA | Lower bounds for asymmetric communication channels and distributed source coding. | Micah Adler, Erik D. Demaine, Nicholas J. A. Harvey, Mihai Patrascu |
| 2006 | SODA | Combination can be hard: approximability of the unique coverage problem. | Erik D. Demaine, Mohammad Taghi Hajiaghayi, Uriel Feige, Mohammad R. Salavatipour |
| 2005 | ESA | Optimizing a 2D Function Satisfying Unimodality Properties. | Erik D. Demaine, Stefan Langerman |
| 2005 | FOCS | Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring. | Erik D. Demaine, Mohammad Taghi Hajiaghayi, Ken-ichi Kawarabayashi |
| 2005 | INFOCOM | Mobile-assisted localization in wireless sensor networks. | Nissanka Bodhi Priyantha, Hari Balakrishnan, Erik D. Demaine, Seth J. Teller |
| 2005 | MOBIHOC | Deploying sensor networks with guaranteed capacity and fault tolerance. | Jonathan Bredin, Erik D. Demaine, Mohammad Taghi Hajiaghayi, Daniela Rus |
| 2005 | SODA | Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics. | Noga Alon, Mihai Badoiu, Erik D. Demaine, Martin Farach-Colton, Mohammad Taghi Hajiaghayi, Anastasios Sidiropoulos |
| 2005 | SODA | Bidimensionality: new connections between FPT algorithms and PTASs. | Erik D. Demaine, Mohammad Taghi Hajiaghayi |
| 2005 | SODA | Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality. | Erik D. Demaine, Mohammad Taghi Hajiaghayi |
| 2005 | SOSP | PersiFS: a versioned file system with an efficient representation. | Dan R. K. Ports, Austin T. Clements, Erik D. Demaine |
| 2005 | WADS | Subquadratic Algorithms for 3SUM. | Ilya Baran, Erik D. Demaine, Mihai Patrascu |
| 2005 | WADS | Communication-Aware Processor Allocation for Supercomputers. | Michael A. Bender, David P. Bunde, Erik D. Demaine, Sndor P. Fekete, Vitus J. Leung, Henk Meijer, Cynthia A. Phillips |
| 2005 | WADS | Hinged Dissection of Polypolyhedra. | Erik D. Demaine, Martin L. Demaine, Jeffrey F. Lindy, Diane L. Souvaine |
| 2004 | FOCS | Dynamic Optimality - Almost. | Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu |
| 2004 | GD | Fast Algorithms for Hard Graph Problems: Bidimensionality, Minors, and Local Treewidth. | Erik D. Demaine, Mohammad Taghi Hajiaghayi |
| 2004 | ISAAC | Puzzles, Art, and Magic with Algorithms. | Erik D. Demaine |
| 2004 | LATIN | A Simplified, Dynamic Unified Structure. | Mihai Badoiu, Erik D. Demaine |
| 2004 | LATIN | Bidimensional Parameters and Local Treewidth. | Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos |
| 2004 | MFCS | The Bidimensional Theory of Bounded-Genus Graphs. | Erik D. Demaine, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos |
| 2004 | SIGGRAPH | Refolding planar polygons. | Hayley N. Iben, James F. O'Brien, Erik D. Demaine |
| 2004 | SODA | Subexponential parameterized algorithms on graphs of bounded-genus and | Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos |
| 2004 | SODA | Equivalence of local treewidth and linear local treewidth and its algorithmic applications. | Erik D. Demaine, Mohammad Taghi Hajiaghayi |
| 2004 | SODA | Retroactive data structures. | Erik D. Demaine, John Iacono, Stefan Langerman |
| 2004 | SODA | Interpolation search for non-independent data. | Erik D. Demaine, Thouis R. Jones, Mihai Patrascu |
| 2004 | SODA | Tight bounds for the partial-sums problem. | Mihai Patrascu, Erik D. Demaine |
| 2004 | STOC | Lower bounds for dynamic connectivity. | Mihai Patrascu, Erik D. Demaine |
| 2004 | SSDBM | Finding Frequent Items in Sliding Windows with Multinomially-Distributed Item Frequencies. | Lukasz Golab, David DeHaan, Alejandro Lpez-Ortiz, Erik D. Demaine |
| 2003 | ALENEX | Open Problems from ALENEX 2003. | Erik D. Demaine |
| 2003 | COCOON | Finding Hidden Independent Sets in Interval Graphs. | Therese Biedl, Brona Brejov, Erik D. Demaine, Angle M. Hamel, Alejandro Lpez-Ortiz, Toms Vinar |
| 2003 | COCOON | Tetris is Hard, Even to Approximate. | Erik D. Demaine, Susan Hohenberger, David Liben-Nowell |
| 2003 | ESA | Optimal Dynamic Video-on-Demand Using Adaptive Broadcasting. | Therese Biedl, Erik D. Demaine, Alexander Golynski, Joseph Douglas Horton, Alejandro Lpez-Ortiz, Guillaume Poirier, Claude-Guy Quimper |
| 2003 | GD | Planar Embeddings of Graphs with Specified Edge Lengths. | Sergio Cabello, Erik D. Demaine, Gnter Rote |
| 2003 | ICALP | Fixed-Parameter Algorithms for the (k, r)-Center in Planar Graphs and Map Graphs. | Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos |
| 2003 | IMC | Identifying frequent items in sliding windows over on-line packet streams. | Lukasz Golab, David DeHaan, Erik D. Demaine, Alejandro Lpez-Ortiz, J. Ian Munro |
| 2003 | ISAAC | Geometric Restrictions on Producible Polygonal Protein Chains. | Erik D. Demaine, Stefan Langerman, Joseph O'Rourke |
| 2003 | SENSYS | Anchor-free distributed localization in sensor networks. | Nissanka Bodhi Priyantha, Hari Balakrishnan, Erik D. Demaine, Seth J. Teller |
| 2003 | WADS | Output-Sensitive Algorithms for Computing Nearest-Neighbour Decision Boundaries. | David Bremner, Erik D. Demaine, Jeff Erickson, John Iacono, Stefan Langerman, Pat Morin, Godfried T. Toussaint |
| 2002 | ESA | Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy. | Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton |
| 2002 | ESA | Two Simplified Algorithms for Maintaining Order in a List. | Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, Jack Zito |
| 2002 | ESA | Efficient Tree Layout in a Multilevel Memory Hierarchy. | Michael A. Bender, Erik D. Demaine, Martin Farach-Colton |
| 2002 | ESA | Frequency Estimation of Internet Packet Streams with Limited Space. | Erik D. Demaine, Alejandro Lpez-Ortiz, J. Ian Munro |
| 2002 | ICALP | The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications. | Robert A. Hearn, Erik D. Demaine |
| 2002 | ISAAC | Flat-State Connectivity of Linkages under Dihedral Motions. | Greg Aloupis, Erik D. Demaine, Vida Dujmovic, Jeff Erickson, Stefan Langerman, Henk Meijer, Joseph O'Rourke, Mark H. Overmars, Michael A. Soss, Ileana Streinu, Godfried T. Toussaint |
| 2002 | ISAAC | Exponential Speedup of Fixed-Parameter Algorithms on K | Erik D. Demaine, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos |
| 2002 | STOC | Cache-oblivious priority queue and graph algorithm applications. | Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, J. Ian Munro |
| 2002 | WABI | K-ary Clustering with Optimal Leaf Ordering for Gene Expression Data. | Ziv Bar-Joseph, Erik D. Demaine, David K. Gifford, Angle M. Hamel, Tommi S. Jaakkola, Nathan Srebro |
| 2001 | ALENEX | Experiments on Adaptive Set Intersections for Text Retrieval Systems. | Erik D. Demaine, Alejandro Lpez-Ortiz, J. Ian Munro |
| 2001 | ISAAC | Tight Bounds on Maximal and Maximum Matchings. | Therese Biedl, Erik D. Demaine, Christian A. Duncan, Rudolf Fleischer, Stephen G. Kobourov |
| 2001 | MFCS | Playing Games with Algorithms: Algorithmic Combinatorial Game Theory. | Erik D. Demaine |
| 2001 | SODA | Optimal covering tours with turn costs. | Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sndor P. Fekete, Joseph S. B. Mitchell, Saurabh Sethia |
| 2001 | SODA | A linear lower bound on index size for text retrieval. | Erik D. Demaine, Alejandro Lpez-Ortiz |
| 2001 | SODA | On universally easy classes for NP-complete problems. | Erik D. Demaine, Alejandro Lpez-Ortiz, J. Ian Munro |
| 2001 | WADS | When Can You Fold a Map? | Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Joseph S. B. Mitchell, Saurabh Sethia, Steven Skiena |
| 2000 | FOCS | Cache-Oblivious B-Trees. | Michael A. Bender, Erik D. Demaine, Martin Farach-Colton |
| 2000 | FOCS | Straighting Polygonal Arcs and Convexifying Polygonal Cycles. | Robert Connelly, Erik D. Demaine, Gnter Rote |
| 2000 | ISAAC | Online Routing in Convex Subdivisions. | Prosenjit Bose, Pat Morin, Andrej Brodnik, Svante Carlsson, Erik D. Demaine, Rudolf Fleischer, J. Ian Munro, Alejandro Lpez-Ortiz |
| 2000 | MFCS | Balanced | Therese C. Biedl, Eowyn Cenek, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer, Ming-wei Wang |
| 2000 | SODA | Adaptive set intersections, unions, and differences. | Erik D. Demaine, Alejandro Lpez-Ortiz, J. Ian Munro |
| 1999 | ISAAC | Convexifying Monotone Polygons. | Therese C. Biedl, Erik D. Demaine, Sylvain Lazard, Steven M. Robbins, Michael A. Soss |
| 1999 | SODA | Efficient Algorithms for Petersen's Matching Theorem. | Therese C. Biedl, Prosenjit Bose, Erik D. Demaine, Anna Lubiw |
| 1999 | SODA | Locked and Unlocked Polygonal Chains in 3D. | Therese Biedl, Erik D. Demaine, Martin L. Demaine, Sylvain Lazard, Anna Lubiw, Joseph O'Rourke, Mark H. Overmars, Steve Robbins, Ileana Streinu, Godfried T. Toussaint, Sue Whitesides |
| 1999 | SODA | Folding and One Straight Cut Suffice. | Erik D. Demaine, Martin L. Demaine, Anna Lubiw |
| 1999 | WADS | Representing Trees of Higer Degree. | David Benoit, Erik D. Demaine, J. Ian Munro, Venkatesh Raman |
| 1999 | WADS | Resizable Arrays in Optimal Time and Space. | Andrej Brodnik, Svante Carlsson, Erik D. Demaine, J. Ian Munro, Robert Sedgewick |
| 1998 | GD | Planar Drawings of Origami Polyhedra. | Erik D. Demaine, Martin L. Demaine |