Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)
Hugo A. Akitaya, Ahmad Biniaz, Erik D. Demaine, Linda Kleist, Frederick Stock, and Csaba D. Tóth. Minimum Plane Bichromatic Spanning Trees. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 4:1-4:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{a.akitaya_et_al:LIPIcs.ISAAC.2024.4, author = {A. Akitaya, Hugo and Biniaz, Ahmad and Demaine, Erik D. and Kleist, Linda and Stock, Frederick and T\'{o}th, Csaba D.}, title = {{Minimum Plane Bichromatic Spanning Trees}}, booktitle = {35th International Symposium on Algorithms and Computation (ISAAC 2024)}, pages = {4:1--4:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-354-6}, ISSN = {1868-8969}, year = {2024}, volume = {322}, editor = {Mestre, Juli\'{a}n and Wirth, Anthony}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.4}, URN = {urn:nbn:de:0030-drops-221319}, doi = {10.4230/LIPIcs.ISAAC.2024.4}, annote = {Keywords: Bichromatic Spanning Tree, Minimum Spanning Tree, Plane Tree} }
Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)
MIT Hardness Group, Josh Brunner, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Markus Hecher, Frederick Stock, and Zixiang Zhou. Easier Ways to Prove Counting Hard: A Dichotomy for Generalized #SAT, Applied to Constraint Graphs. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 51:1-51:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mithardnessgroup_et_al:LIPIcs.ISAAC.2024.51, author = {MIT Hardness Group and Brunner, Josh and Demaine, Erik D. and Diomidova, Jenny and Gomez, Timothy and Hecher, Markus and Stock, Frederick and Zhou, Zixiang}, title = {{Easier Ways to Prove Counting Hard: A Dichotomy for Generalized #SAT, Applied to Constraint Graphs}}, booktitle = {35th International Symposium on Algorithms and Computation (ISAAC 2024)}, pages = {51:1--51:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-354-6}, ISSN = {1868-8969}, year = {2024}, volume = {322}, editor = {Mestre, Juli\'{a}n and Wirth, Anthony}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.51}, URN = {urn:nbn:de:0030-drops-221790}, doi = {10.4230/LIPIcs.ISAAC.2024.51}, annote = {Keywords: Counting, Computational Complexity, Sharp-P, Dichotomy, Constraint Graph Satisfiability} }
Published in: LIPIcs, Volume 314, 30th International Conference on DNA Computing and Molecular Programming (DNA 30) (2024)
Erik D. Demaine, Timothy Gomez, Elise Grizzell, Markus Hecher, Jayson Lynch, Robert Schweller, Ahmed Shalaby, and Damien Woods. Domain-Based Nucleic-Acid Minimum Free Energy: Algorithmic Hardness and Parameterized Bounds. In 30th International Conference on DNA Computing and Molecular Programming (DNA 30). Leibniz International Proceedings in Informatics (LIPIcs), Volume 314, pp. 2:1-2:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{demaine_et_al:LIPIcs.DNA.30.2, author = {Demaine, Erik D. and Gomez, Timothy and Grizzell, Elise and Hecher, Markus and Lynch, Jayson and Schweller, Robert and Shalaby, Ahmed and Woods, Damien}, title = {{Domain-Based Nucleic-Acid Minimum Free Energy: Algorithmic Hardness and Parameterized Bounds}}, booktitle = {30th International Conference on DNA Computing and Molecular Programming (DNA 30)}, pages = {2:1--2:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-344-7}, ISSN = {1868-8969}, year = {2024}, volume = {314}, editor = {Seki, Shinnosuke and Stewart, Jaimie Marie}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.30.2}, URN = {urn:nbn:de:0030-drops-209304}, doi = {10.4230/LIPIcs.DNA.30.2}, annote = {Keywords: Domain-based DNA designs, minimum free energy, efficient algorithms, NP-hard, P-hard, NC, fixed-parameter tractable} }
Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)
MIT-NASA Space Robots Team, Josh Brunner, Kenneth C. Cheung, Erik D. Demaine, Jenny Diomidova, Christine Gregg, Della H. Hendrickson, and Irina Kostitsyna. Reconfiguration Algorithms for Cubic Modular Robots with Realistic Movement Constraints. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 34:1-34:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mitnasaspacerobotsteam_et_al:LIPIcs.SWAT.2024.34, author = {MIT-NASA Space Robots Team and Brunner, Josh and Cheung, Kenneth C. and Demaine, Erik D. and Diomidova, Jenny and Gregg, Christine and Hendrickson, Della H. and Kostitsyna, Irina}, title = {{Reconfiguration Algorithms for Cubic Modular Robots with Realistic Movement Constraints}}, booktitle = {19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)}, pages = {34:1--34:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-318-8}, ISSN = {1868-8969}, year = {2024}, volume = {294}, editor = {Bodlaender, Hans L.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.34}, URN = {urn:nbn:de:0030-drops-200742}, doi = {10.4230/LIPIcs.SWAT.2024.34}, annote = {Keywords: Modular robotics, programmable matter, digital materials, motion planning} }
Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)
MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, and Matias Korman. PSPACE-Hard 2D Super Mario Games: Thirteen Doors. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mithardnessgroup_et_al:LIPIcs.FUN.2024.21, author = {MIT Hardness Group and Ani, Hayashi and Demaine, Erik D. and Hall, Holden and Korman, Matias}, title = {{PSPACE-Hard 2D Super Mario Games: Thirteen Doors}}, booktitle = {12th International Conference on Fun with Algorithms (FUN 2024)}, pages = {21:1--21:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-314-0}, ISSN = {1868-8969}, year = {2024}, volume = {291}, editor = {Broder, Andrei Z. and Tamir, Tami}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.21}, URN = {urn:nbn:de:0030-drops-199295}, doi = {10.4230/LIPIcs.FUN.2024.21}, annote = {Keywords: video games, computational complexity, PSPACE} }
Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)
MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, Ricardo Ruiz, and Naveen Venkat. You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mithardnessgroup_et_al:LIPIcs.FUN.2024.22, author = {MIT Hardness Group and Ani, Hayashi and Demaine, Erik D. and Hall, Holden and Ruiz, Ricardo and Venkat, Naveen}, title = {{You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games}}, booktitle = {12th International Conference on Fun with Algorithms (FUN 2024)}, pages = {22:1--22:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-314-0}, ISSN = {1868-8969}, year = {2024}, volume = {291}, editor = {Broder, Andrei Z. and Tamir, Tami}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.22}, URN = {urn:nbn:de:0030-drops-199302}, doi = {10.4230/LIPIcs.FUN.2024.22}, annote = {Keywords: video games, computational complexity, undecidability} }
Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)
MIT Hardness Group, Josh Brunner, Lily Chung, Erik D. Demaine, Della Hendrickson, and Andy Tockman. ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 23:1-23:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mithardnessgroup_et_al:LIPIcs.FUN.2024.23, author = {MIT Hardness Group and Brunner, Josh and Chung, Lily and Demaine, Erik D. and Hendrickson, Della and Tockman, Andy}, title = {{ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles}}, booktitle = {12th International Conference on Fun with Algorithms (FUN 2024)}, pages = {23:1--23:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-314-0}, ISSN = {1868-8969}, year = {2024}, volume = {291}, editor = {Broder, Andrei Z. and Tamir, Tami}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.23}, URN = {urn:nbn:de:0030-drops-199314}, doi = {10.4230/LIPIcs.FUN.2024.23}, annote = {Keywords: pencil-and-paper puzzles, computational complexity, parsimony} }
Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)
MIT Hardness Group, Erik D. Demaine, Holden Hall, and Jeffery Li. Tetris with Few Piece Types. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mithardnessgroup_et_al:LIPIcs.FUN.2024.24, author = {MIT Hardness Group and Demaine, Erik D. and Hall, Holden and Li, Jeffery}, title = {{Tetris with Few Piece Types}}, booktitle = {12th International Conference on Fun with Algorithms (FUN 2024)}, pages = {24:1--24:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-314-0}, ISSN = {1868-8969}, year = {2024}, volume = {291}, editor = {Broder, Andrei Z. and Tamir, Tami}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.24}, URN = {urn:nbn:de:0030-drops-199322}, doi = {10.4230/LIPIcs.FUN.2024.24}, annote = {Keywords: complexity, hardness, video games, counting} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Erik D. Demaine, Yael Kirkpatrick, and Rebecca Lin. Graph Threading. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 38:1-38:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{demaine_et_al:LIPIcs.ITCS.2024.38, author = {Demaine, Erik D. and Kirkpatrick, Yael and Lin, Rebecca}, title = {{Graph Threading}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {38:1--38:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.38}, URN = {urn:nbn:de:0030-drops-195665}, doi = {10.4230/LIPIcs.ITCS.2024.38}, annote = {Keywords: Shortest walk, Eulerian cycle, perfect matching, beading} }
Published in: LIPIcs, Volume 276, 29th International Conference on DNA Computing and Molecular Programming (DNA 29) (2023)
Robert M. Alaniz, Josh Brunner, Michael Coulombe, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Elise Grizzell, Ryan Knobel, Jayson Lynch, Andrew Rodriguez, Robert Schweller, and Tim Wylie. Complexity of Reconfiguration in Surface Chemical Reaction Networks. In 29th International Conference on DNA Computing and Molecular Programming (DNA 29). Leibniz International Proceedings in Informatics (LIPIcs), Volume 276, pp. 10:1-10:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{alaniz_et_al:LIPIcs.DNA.29.10, author = {Alaniz, Robert M. and Brunner, Josh and Coulombe, Michael and Demaine, Erik D. and Diomidova, Jenny and Gomez, Timothy and Grizzell, Elise and Knobel, Ryan and Lynch, Jayson and Rodriguez, Andrew and Schweller, Robert and Wylie, Tim}, title = {{Complexity of Reconfiguration in Surface Chemical Reaction Networks}}, booktitle = {29th International Conference on DNA Computing and Molecular Programming (DNA 29)}, pages = {10:1--10:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-297-6}, ISSN = {1868-8969}, year = {2023}, volume = {276}, editor = {Chen, Ho-Lin and Evans, Constantine G.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.29.10}, URN = {urn:nbn:de:0030-drops-187936}, doi = {10.4230/LIPIcs.DNA.29.10}, annote = {Keywords: Chemical Reaction Networks, reconfiguration, hardness} }
Published in: LIPIcs, Volume 257, 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)
Joshua Ani, Michael Coulombe, Erik D. Demaine, Yevhenii Diomidov, Timothy Gomez, Dylan Hendrickson, and Jayson Lynch. Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 257, pp. 5:1-5:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{ani_et_al:LIPIcs.SAND.2023.5, author = {Ani, Joshua and Coulombe, Michael and Demaine, Erik D. and Diomidov, Yevhenii and Gomez, Timothy and Hendrickson, Dylan and Lynch, Jayson}, title = {{Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines}}, booktitle = {2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023)}, pages = {5:1--5:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-275-4}, ISSN = {1868-8969}, year = {2023}, volume = {257}, editor = {Doty, David and Spirakis, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2023.5}, URN = {urn:nbn:de:0030-drops-179414}, doi = {10.4230/LIPIcs.SAND.2023.5}, annote = {Keywords: Gadgets, robots, undecidability, Petri nets} }
Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Lily Chung, Erik D. Demaine, Dylan Hendrickson, and Jayson Lynch. Lower Bounds on Retroactive Data Structures. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 32:1-32:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{chung_et_al:LIPIcs.ISAAC.2022.32, author = {Chung, Lily and Demaine, Erik D. and Hendrickson, Dylan and Lynch, Jayson}, title = {{Lower Bounds on Retroactive Data Structures}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {32:1--32:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.32}, URN = {urn:nbn:de:0030-drops-173171}, doi = {10.4230/LIPIcs.ISAAC.2022.32}, annote = {Keywords: Retroactivity, time travel, rollback, fine-grained complexity} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Oswin Aichholzer, Erik D. Demaine, Matias Korman, Anna Lubiw, Jayson Lynch, Zuzana Masárová, Mikhail Rudoy, Virginia Vassilevska Williams, and Nicole Wein. Hardness of Token Swapping on Trees. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{aichholzer_et_al:LIPIcs.ESA.2022.3, author = {Aichholzer, Oswin and Demaine, Erik D. and Korman, Matias and Lubiw, Anna and Lynch, Jayson and Mas\'{a}rov\'{a}, Zuzana and Rudoy, Mikhail and Vassilevska Williams, Virginia and Wein, Nicole}, title = {{Hardness of Token Swapping on Trees}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {3:1--3:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.3}, URN = {urn:nbn:de:0030-drops-169413}, doi = {10.4230/LIPIcs.ESA.2022.3}, annote = {Keywords: Sorting, Token swapping, Trees, NP-hard, Approximation} }
Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)
Hugo A. Akitaya, Erik D. Demaine, Matias Korman, Irina Kostitsyna, Irene Parada, Willem Sonke, Bettina Speckmann, Ryuhei Uehara, and Jules Wulms. Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{a.akitaya_et_al:LIPIcs.SWAT.2022.4, author = {A. Akitaya, Hugo and Demaine, Erik D. and Korman, Matias and Kostitsyna, Irina and Parada, Irene and Sonke, Willem and Speckmann, Bettina and Uehara, Ryuhei and Wulms, Jules}, title = {{Compacting Squares: Input-Sensitive In-Place Reconfiguration of Sliding Squares}}, booktitle = {18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)}, pages = {4:1--4:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-236-5}, ISSN = {1868-8969}, year = {2022}, volume = {227}, editor = {Czumaj, Artur and Xin, Qin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.4}, URN = {urn:nbn:de:0030-drops-161644}, doi = {10.4230/LIPIcs.SWAT.2022.4}, annote = {Keywords: Sliding cubes, Reconfiguration, Modular robots, NP-hardness} }
Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)
Lily Chung, Erik D. Demaine, Dylan Hendrickson, and Victor Luo. Flat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) Without Flat Angles. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{chung_et_al:LIPIcs.SoCG.2022.29, author = {Chung, Lily and Demaine, Erik D. and Hendrickson, Dylan and Luo, Victor}, title = {{Flat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) Without Flat Angles}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {29:1--29:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.29}, URN = {urn:nbn:de:0030-drops-160371}, doi = {10.4230/LIPIcs.SoCG.2022.29}, annote = {Keywords: Graph drawing, folding, origami, polyhedral complex, algorithms} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Joshua Ani, Lily Chung, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson, and Jayson Lynch. Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 3:1-3:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ani_et_al:LIPIcs.FUN.2022.3, author = {Ani, Joshua and Chung, Lily and Demaine, Erik D. and Diomidov, Yevhenii and Hendrickson, Dylan and Lynch, Jayson}, title = {{Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {3:1--3:30}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.3}, URN = {urn:nbn:de:0030-drops-159737}, doi = {10.4230/LIPIcs.FUN.2022.3}, annote = {Keywords: gadgets, motion planning, hardness of games} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Akira Baes, Erik D. Demaine, Martin L. Demaine, Elizabeth Hartung, Stefan Langerman, Joseph O'Rourke, Ryuhei Uehara, Yushi Uno, and Aaron Williams. Rolling Polyhedra on Tessellations. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{baes_et_al:LIPIcs.FUN.2022.6, author = {Baes, Akira and Demaine, Erik D. and Demaine, Martin L. and Hartung, Elizabeth and Langerman, Stefan and O'Rourke, Joseph and Uehara, Ryuhei and Uno, Yushi and Williams, Aaron}, title = {{Rolling Polyhedra on Tessellations}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {6:1--6:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.6}, URN = {urn:nbn:de:0030-drops-159761}, doi = {10.4230/LIPIcs.FUN.2022.6}, annote = {Keywords: polyhedra, tilings} }
Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)
Hugo A. Akitaya, Erik D. Demaine, Andrei Gonczi, Dylan H. Hendrickson, Adam Hesterberg, Matias Korman, Oliver Korten, Jayson Lynch, Irene Parada, and Vera Sacristán. Characterizing Universal Reconfigurability of Modular Pivoting Robots. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{a.akitaya_et_al:LIPIcs.SoCG.2021.10, author = {A. Akitaya, Hugo and Demaine, Erik D. and Gonczi, Andrei and Hendrickson, Dylan H. and Hesterberg, Adam and Korman, Matias and Korten, Oliver and Lynch, Jayson and Parada, Irene and Sacrist\'{a}n, Vera}, title = {{Characterizing Universal Reconfigurability of Modular Pivoting Robots}}, booktitle = {37th International Symposium on Computational Geometry (SoCG 2021)}, pages = {10:1--10:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-184-9}, ISSN = {1868-8969}, year = {2021}, volume = {189}, editor = {Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.10}, URN = {urn:nbn:de:0030-drops-138094}, doi = {10.4230/LIPIcs.SoCG.2021.10}, annote = {Keywords: reconfiguration, geometric algorithm, PSPACE-hardness, pivoting hexagons, pivoting squares, modular robots} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
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, and Lillian Zhang. Arithmetic Expression Construction. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{alcock_et_al:LIPIcs.ISAAC.2020.12, author = {Alcock, Leo and Asif, Sualeh and Bosboom, Jeffrey and Brunner, Josh and Chen, Charlotte and Demaine, Erik D. and Epstein, Rogers and Hesterberg, Adam and Hirschfeld, Lior and Hu, William and Lynch, Jayson and Scheffler, Sarah and Zhang, Lillian}, title = {{Arithmetic Expression Construction}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {12:1--12:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.12}, URN = {urn:nbn:de:0030-drops-133568}, doi = {10.4230/LIPIcs.ISAAC.2020.12}, annote = {Keywords: Hardness, algebraic complexity, expression trees} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Josh Brunner, Erik D. Demaine, Dylan Hendrickson, and Julian Wellman. Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{brunner_et_al:LIPIcs.ISAAC.2020.17, author = {Brunner, Josh and Demaine, Erik D. and Hendrickson, Dylan and Wellman, Julian}, title = {{Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess Is Hard}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {17:1--17:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.17}, URN = {urn:nbn:de:0030-drops-133618}, doi = {10.4230/LIPIcs.ISAAC.2020.17}, annote = {Keywords: hardness, board games, PSPACE} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Erik D. Demaine, Justin Kopinsky, and Jayson Lynch. Recursed Is Not Recursive: A Jarring Result. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{demaine_et_al:LIPIcs.ISAAC.2020.50, author = {Demaine, Erik D. and Kopinsky, Justin and Lynch, Jayson}, title = {{Recursed Is Not Recursive: A Jarring Result}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {50:1--50:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.50}, URN = {urn:nbn:de:0030-drops-133940}, doi = {10.4230/LIPIcs.ISAAC.2020.50}, annote = {Keywords: Computational Complexity, Undecidable, Video Games} }
Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)
Aviv Adler, Jeffrey Bosboom, Erik D. Demaine, Martin L. Demaine, Quanquan C. Liu, and Jayson Lynch. Tatamibari Is NP-Complete. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{adler_et_al:LIPIcs.FUN.2021.1, author = {Adler, Aviv and Bosboom, Jeffrey and Demaine, Erik D. and Demaine, Martin L. and Liu, Quanquan C. and Lynch, Jayson}, title = {{Tatamibari Is NP-Complete}}, booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)}, pages = {1:1--1:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-145-0}, ISSN = {1868-8969}, year = {2020}, volume = {157}, editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.1}, URN = {urn:nbn:de:0030-drops-127624}, doi = {10.4230/LIPIcs.FUN.2021.1}, annote = {Keywords: Nikoli puzzles, NP-hardness, rectangle covering} }
Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)
Joshua Ani, Jeffrey Bosboom, Erik D. Demaine, Yenhenii Diomidov, Dylan Hendrickson, and Jayson Lynch. Walking Through Doors Is Hard, Even Without Staircases: Proving PSPACE-Hardness via Planar Assemblies of Door Gadgets. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 3:1-3:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{ani_et_al:LIPIcs.FUN.2021.3, author = {Ani, Joshua and Bosboom, Jeffrey and Demaine, Erik D. and Diomidov, Yenhenii and Hendrickson, Dylan and Lynch, Jayson}, title = {{Walking Through Doors Is Hard, Even Without Staircases: Proving PSPACE-Hardness via Planar Assemblies of Door Gadgets}}, booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)}, pages = {3:1--3:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-145-0}, ISSN = {1868-8969}, year = {2020}, volume = {157}, editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.3}, URN = {urn:nbn:de:0030-drops-127642}, doi = {10.4230/LIPIcs.FUN.2021.3}, annote = {Keywords: gadgets, motion planning, hardness of games} }
Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)
Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff. 1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{brunner_et_al:LIPIcs.FUN.2021.7, author = {Brunner, Josh and Chung, Lily and Demaine, Erik D. and Hendrickson, Dylan and Hesterberg, Adam and Suhl, Adam and Zeff, Avi}, title = {{1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete}}, booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)}, pages = {7:1--7:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-145-0}, ISSN = {1868-8969}, year = {2020}, volume = {157}, editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.7}, URN = {urn:nbn:de:0030-drops-127681}, doi = {10.4230/LIPIcs.FUN.2021.7}, annote = {Keywords: puzzles, sliding blocks, PSPACE-hardness} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Erik D. Demaine, Adam C. Hesterberg, and Jason S. Ku. Finding Closed Quasigeodesics on Convex Polyhedra. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 33:1-33:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{demaine_et_al:LIPIcs.SoCG.2020.33, author = {Demaine, Erik D. and Hesterberg, Adam C. and Ku, Jason S.}, title = {{Finding Closed Quasigeodesics on Convex Polyhedra}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {33:1--33:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-143-6}, ISSN = {1868-8969}, year = {2020}, volume = {164}, editor = {Cabello, Sergio and Chen, Danny Z.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.33}, URN = {urn:nbn:de:0030-drops-121912}, doi = {10.4230/LIPIcs.SoCG.2020.33}, annote = {Keywords: polyhedra, geodesic, pseudopolynomial, geometric precision} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Erik D. Demaine, Dylan H. Hendrickson, and Jayson Lynch. Toward a General Complexity Theory of Motion Planning: Characterizing Which Gadgets Make Games Hard. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 62:1-62:42, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{demaine_et_al:LIPIcs.ITCS.2020.62, author = {Demaine, Erik D. and Hendrickson, Dylan H. and Lynch, Jayson}, title = {{Toward a General Complexity Theory of Motion Planning: Characterizing Which Gadgets Make Games Hard}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {62:1--62:42}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.62}, URN = {urn:nbn:de:0030-drops-117478}, doi = {10.4230/LIPIcs.ITCS.2020.62}, annote = {Keywords: motion planning, computational complexity, NP, PSPACE, EXP, NEXP, undecidability, games} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Hugo A. Akitaya, Esther M. Arkin, Mirela Damian, Erik D. Demaine, Vida Dujmović, Robin Flatland, Matias Korman, Belen Palop, Irene Parada, André van Renssen, and Vera Sacristán. Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{akitaya_et_al:LIPIcs.ESA.2019.3, author = {Akitaya, Hugo A. and Arkin, Esther M. and Damian, Mirela and Demaine, Erik D. and Dujmovi\'{c}, Vida and Flatland, Robin and Korman, Matias and Palop, Belen and Parada, Irene and van Renssen, Andr\'{e} and Sacrist\'{a}n, Vera}, title = {{Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {3:1--3:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.3}, URN = {urn:nbn:de:0030-drops-111247}, doi = {10.4230/LIPIcs.ESA.2019.3}, annote = {Keywords: Reconfiguration, geometric algorithm, pivoting squares, modular robots} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Erik D. Demaine, Timothy D. Goodrich, Kyle Kloster, Brian Lavallee, Quanquan C. Liu, Blair D. Sullivan, Ali Vakilian, and Andrew van der Poel. Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{demaine_et_al:LIPIcs.ESA.2019.37, author = {Demaine, Erik D. and Goodrich, Timothy D. and Kloster, Kyle and Lavallee, Brian and Liu, Quanquan C. and Sullivan, Blair D. and Vakilian, Ali and van der Poel, Andrew}, title = {{Structural Rounding: Approximation Algorithms for Graphs Near an Algorithmically Tractable Class}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {37:1--37:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.37}, URN = {urn:nbn:de:0030-drops-111583}, doi = {10.4230/LIPIcs.ESA.2019.37}, annote = {Keywords: structural rounding, graph editing, approximation algorithms} }
Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)
Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Christian Scheffer, and Henk Meijer. Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{demaine_et_al:LIPIcs.SoCG.2018.29, author = {Demaine, Erik D. and Fekete, S\'{a}ndor P. and Keldenich, Phillip and Scheffer, Christian and Meijer, Henk}, title = {{Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch}}, booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)}, pages = {29:1--29:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-066-8}, ISSN = {1868-8969}, year = {2018}, volume = {99}, editor = {Speckmann, Bettina and T\'{o}th, Csaba D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.29}, URN = {urn:nbn:de:0030-drops-87423}, doi = {10.4230/LIPIcs.SoCG.2018.29}, annote = {Keywords: Robot swarms, coordinated motion planning, parallel motion, makespan, bounded stretch, complexity, approximation} }
Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)
Zachary Abel, Jeffrey Bosboom, Erik D. Demaine, Linus Hamilton, Adam Hesterberg, Justin Kopinsky, Jayson Lynch, and Mikhail Rudoy. Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 3:1-3:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{abel_et_al:LIPIcs.FUN.2018.3, author = {Abel, Zachary and Bosboom, Jeffrey and Demaine, Erik D. and Hamilton, Linus and Hesterberg, Adam and Kopinsky, Justin and Lynch, Jayson and Rudoy, Mikhail}, title = {{Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {3:1--3:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-067-5}, ISSN = {1868-8969}, year = {2018}, volume = {100}, editor = {Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.3}, URN = {urn:nbn:de:0030-drops-87944}, doi = {10.4230/LIPIcs.FUN.2018.3}, annote = {Keywords: video games, puzzles, hardness} }
Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)
Jeffrey Bosboom, Erik D. Demaine, and Mikhail Rudoy. Computational Complexity of Generalized Push Fight. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 11:1-11:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bosboom_et_al:LIPIcs.FUN.2018.11, author = {Bosboom, Jeffrey and Demaine, Erik D. and Rudoy, Mikhail}, title = {{Computational Complexity of Generalized Push Fight}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {11:1--11:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-067-5}, ISSN = {1868-8969}, year = {2018}, volume = {100}, editor = {Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.11}, URN = {urn:nbn:de:0030-drops-88029}, doi = {10.4230/LIPIcs.FUN.2018.11}, annote = {Keywords: board games, hardness, mate-in-one} }
Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)
Erik D. Demaine, Isaac Grosof, Jayson Lynch, and Mikhail Rudoy. Computational Complexity of Motion Planning of a Robot through Simple Gadgets. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 18:1-18:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{demaine_et_al:LIPIcs.FUN.2018.18, author = {Demaine, Erik D. and Grosof, Isaac and Lynch, Jayson and Rudoy, Mikhail}, title = {{Computational Complexity of Motion Planning of a Robot through Simple Gadgets}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {18:1--18:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-067-5}, ISSN = {1868-8969}, year = {2018}, volume = {100}, editor = {Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.18}, URN = {urn:nbn:de:0030-drops-88098}, doi = {10.4230/LIPIcs.FUN.2018.18}, annote = {Keywords: PSPACE, hardness, motion planning, puzzles} }
Published in: LIPIcs, Volume 100, 9th International Conference on Fun with Algorithms (FUN 2018)
Erik D. Demaine, Joshua Lockhart, and Jayson Lynch. The Computational Complexity of Portal and Other 3D Video Games. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 19:1-19:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{demaine_et_al:LIPIcs.FUN.2018.19, author = {Demaine, Erik D. and Lockhart, Joshua and Lynch, Jayson}, title = {{The Computational Complexity of Portal and Other 3D Video Games}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {19:1--19:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-067-5}, ISSN = {1868-8969}, year = {2018}, volume = {100}, editor = {Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.19}, URN = {urn:nbn:de:0030-drops-88104}, doi = {10.4230/LIPIcs.FUN.2018.19}, annote = {Keywords: video games, hardness, motion planning, NP, PSPACE} }
Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Erik D. Demaine and Mikhail Rudoy. Tree-Residue Vertex-Breaking: a new tool for proving hardness. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{demaine_et_al:LIPIcs.SWAT.2018.32, author = {Demaine, Erik D. and Rudoy, Mikhail}, title = {{Tree-Residue Vertex-Breaking: a new tool for proving hardness}}, booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)}, pages = {32:1--32:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-068-2}, ISSN = {1868-8969}, year = {2018}, volume = {101}, editor = {Eppstein, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.32}, URN = {urn:nbn:de:0030-drops-88586}, doi = {10.4230/LIPIcs.SWAT.2018.32}, annote = {Keywords: NP-hardness, graphs, Hamiltonicity, hypergraph spanning tree} }
Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Lijie Chen, Erik D. Demaine, Yuzhou Gu, Virginia Vassilevska Williams, Yinzhan Xu, and Yuancheng Yu. Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 33:1-33:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chen_et_al:LIPIcs.SWAT.2018.33, author = {Chen, Lijie and Demaine, Erik D. and Gu, Yuzhou and Williams, Virginia Vassilevska and Xu, Yinzhan and Yu, Yuancheng}, title = {{Nearly Optimal Separation Between Partially and Fully Retroactive Data Structures}}, booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)}, pages = {33:1--33:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-068-2}, ISSN = {1868-8969}, year = {2018}, volume = {101}, editor = {Eppstein, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.33}, URN = {urn:nbn:de:0030-drops-88593}, doi = {10.4230/LIPIcs.SWAT.2018.33}, annote = {Keywords: retroactive data structure, conditional lower bound} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Erik D. Demaine, Sarah Eisenstat, and Mikhail Rudoy. Solving the Rubik's Cube Optimally is NP-complete. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{demaine_et_al:LIPIcs.STACS.2018.24, author = {Demaine, Erik D. and Eisenstat, Sarah and Rudoy, Mikhail}, title = {{Solving the Rubik's Cube Optimally is NP-complete}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {24:1--24:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.24}, URN = {urn:nbn:de:0030-drops-85336}, doi = {10.4230/LIPIcs.STACS.2018.24}, annote = {Keywords: combinatorial puzzles, NP-hardness, group theory, Hamiltonicity} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Erik D. Demaine, Andrea Lincoln, Quanquan C. Liu, Jayson Lynch, and Virginia Vassilevska Williams. Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 34:1-34:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{demaine_et_al:LIPIcs.ITCS.2018.34, author = {Demaine, Erik D. and Lincoln, Andrea and Liu, Quanquan C. and Lynch, Jayson and Vassilevska Williams, Virginia}, title = {{Fine-grained I/O Complexity via Reductions: New Lower Bounds, Faster Algorithms, and a Time Hierarchy}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {34:1--34:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.34}, URN = {urn:nbn:de:0030-drops-83335}, doi = {10.4230/LIPIcs.ITCS.2018.34}, annote = {Keywords: IO model, Fine-grained Complexity, Algorithms} }
Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)
Erik D. Demaine and Tomohiro Tachi. Origamizer: A Practical Algorithm for Folding Any Polyhedron. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{demaine_et_al:LIPIcs.SoCG.2017.34, author = {Demaine, Erik D. and Tachi, Tomohiro}, title = {{Origamizer: A Practical Algorithm for Folding Any Polyhedron}}, booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)}, pages = {34:1--34:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-038-5}, ISSN = {1868-8969}, year = {2017}, volume = {77}, editor = {Aronov, Boris and Katz, Matthew J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.34}, URN = {urn:nbn:de:0030-drops-72315}, doi = {10.4230/LIPIcs.SoCG.2017.34}, annote = {Keywords: origami, folding, polyhedra, Voronoi diagram, computational geometry} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Aviv Adler, Constantinos Daskalakis, and Erik D. Demaine. The Complexity of Hex and the Jordan Curve Theorem. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{adler_et_al:LIPIcs.ICALP.2016.24, author = {Adler, Aviv and Daskalakis, Constantinos and Demaine, Erik D.}, title = {{The Complexity of Hex and the Jordan Curve Theorem}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {24:1--24:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.24}, URN = {urn:nbn:de:0030-drops-63032}, doi = {10.4230/LIPIcs.ICALP.2016.24}, annote = {Keywords: Jordan, Brouwer, Hex, PPAD, PSPACE} }
Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)
8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@Proceedings{demaine_et_al:LIPIcs.FUN.2016, title = {{LIPIcs, Volume 49, FUN'16, Complete Volume}}, booktitle = {8th International Conference on Fun with Algorithms (FUN 2016)}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-005-7}, ISSN = {1868-8969}, year = {2016}, volume = {49}, editor = {Demaine, Erik D. and Grandoni, Fabrizio}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016}, URN = {urn:nbn:de:0030-drops-60579}, doi = {10.4230/LIPIcs.FUN.2016}, annote = {Keywords: Nonnumerical Algorithms and Problems, Discrete Mathematics, Complexity Measures and Classes} }
Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)
Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, and Tao B. Schardl. Who Needs Crossings? Hardness of Plane Graph Rigidity. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 3:1-3:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{abel_et_al:LIPIcs.SoCG.2016.3, author = {Abel, Zachary and Demaine, Erik D. and Demaine, Martin L. and Eisenstat, Sarah and Lynch, Jayson and Schardl, Tao B.}, title = {{Who Needs Crossings? Hardness of Plane Graph Rigidity}}, booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)}, pages = {3:1--3:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-009-5}, ISSN = {1868-8969}, year = {2016}, volume = {51}, editor = {Fekete, S\'{a}ndor and Lubiw, Anna}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.3}, URN = {urn:nbn:de:0030-drops-58951}, doi = {10.4230/LIPIcs.SoCG.2016.3}, annote = {Keywords: Graph Drawing, Graph Rigidity Theory, Graph Global Rigidity, Linkages, Complexity Theory, Computational Geometry} }
Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)
8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{demaine_et_al:LIPIcs.FUN.2016.0, author = {Demaine, Erik D. and Grandoni, Fabrizio}, title = {{Front Matter, Table of Contents, Preface, Conference Organization}}, booktitle = {8th International Conference on Fun with Algorithms (FUN 2016)}, pages = {0:i--0:xvi}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-005-7}, ISSN = {1868-8969}, year = {2016}, volume = {49}, editor = {Demaine, Erik D. and Grandoni, Fabrizio}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.0}, URN = {urn:nbn:de:0030-drops-58624}, doi = {10.4230/LIPIcs.FUN.2016.0}, annote = {Keywords: Front Matter, Table of Contents, Preface, Conference Organization} }
Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)
Erik D. Demaine, Fermi Ma, Ariel Schvartzman, Erik Waingarten, and Scott Aaronson. The Fewest Clues Problem. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 12:1-12:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{demaine_et_al:LIPIcs.FUN.2016.12, author = {Demaine, Erik D. and Ma, Fermi and Schvartzman, Ariel and Waingarten, Erik and Aaronson, Scott}, title = {{The Fewest Clues Problem}}, booktitle = {8th International Conference on Fun with Algorithms (FUN 2016)}, pages = {12:1--12:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-005-7}, ISSN = {1868-8969}, year = {2016}, volume = {49}, editor = {Demaine, Erik D. and Grandoni, Fabrizio}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.12}, URN = {urn:nbn:de:0030-drops-58654}, doi = {10.4230/LIPIcs.FUN.2016.12}, annote = {Keywords: computational complexity, pencil-and-paper puzzles, hardness reductions} }
Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)
Erik D. Demaine, Giovanni Viglietta, and Aaron Williams. Super Mario Bros. is Harder/Easier Than We Thought. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{demaine_et_al:LIPIcs.FUN.2016.13, author = {Demaine, Erik D. and Viglietta, Giovanni and Williams, Aaron}, title = {{Super Mario Bros. is Harder/Easier Than We Thought}}, booktitle = {8th International Conference on Fun with Algorithms (FUN 2016)}, pages = {13:1--13:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-005-7}, ISSN = {1868-8969}, year = {2016}, volume = {49}, editor = {Demaine, Erik D. and Grandoni, Fabrizio}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.13}, URN = {urn:nbn:de:0030-drops-58802}, doi = {10.4230/LIPIcs.FUN.2016.13}, annote = {Keywords: video games, computational complexity, PSPACE} }
Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)
Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete, Hamed Mohtasham Shad, and Rose Morris-Wright. Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 16-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{becker_et_al:LIPIcs.SOCG.2015.16, author = {Becker, Aaron T. and Demaine, Erik D. and Fekete, S\'{a}ndor P. and Shad, Hamed Mohtasham and Morris-Wright, Rose}, title = {{Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals}}, booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, pages = {16--18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-83-5}, ISSN = {1868-8969}, year = {2015}, volume = {34}, editor = {Arge, Lars and Pach, J\'{a}nos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.16}, URN = {urn:nbn:de:0030-drops-50870}, doi = {10.4230/LIPIcs.SOCG.2015.16}, annote = {Keywords: Particle swarms, global control, complexity, geometric computation} }
Published in: Dagstuhl Reports, Volume 3, Issue 3 (2013)
Erik D. Demaine, Fedor V. Fomin, MohammadTaghi Hajiaghayi, and Dimitrios M. Thilikos. Bidimensional Structures: Algorithms, Combinatorics and Logic (Dagstuhl Seminar 13121). In Dagstuhl Reports, Volume 3, Issue 3, pp. 51-74, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@Article{demaine_et_al:DagRep.3.3.51, author = {Demaine, Erik D. and Fomin, Fedor V. and Hajiaghayi, MohammadTaghi and Thilikos, Dimitrios M.}, title = {{Bidimensional Structures: Algorithms, Combinatorics and Logic (Dagstuhl Seminar 13121)}}, pages = {51--74}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2013}, volume = {3}, number = {3}, editor = {Demaine, Erik D. and Fomin, Fedor V. and Hajiaghayi, MohammadTaghi and Thilikos, Dimitrios M.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.3.51}, URN = {urn:nbn:de:0030-drops-40131}, doi = {10.4230/DagRep.3.3.51}, annote = {Keywords: Graph Minors, Treewidth, Graph algorithms, Parameterized Algorithms} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert T. Schweller, Scott M Summers, and Andrew Winslow. Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 172-184, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{cannon_et_al:LIPIcs.STACS.2013.172, author = {Cannon, Sarah and Demaine, Erik D. and Demaine, Martin L. and Eisenstat, Sarah and Patitz, Matthew J. and Schweller, Robert T. and Summers, Scott M and Winslow, Andrew}, title = {{Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {172--184}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.172}, URN = {urn:nbn:de:0030-drops-39321}, doi = {10.4230/LIPIcs.STACS.2013.172}, annote = {Keywords: abstract tile assembly model, hierarchical tile assembly model, two-handed tile assembly model, algorithmic self-assembly, DNA computing, biocomputing} }
Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw, André Schulz, Diane L. Souvaine, Giovanni Viglietta, and Andrew Winslow. Algorithms for Designing Pop-Up Cards. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 269-280, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)
@InProceedings{abel_et_al:LIPIcs.STACS.2013.269, author = {Abel, Zachary and Demaine, Erik D. and Demaine, Martin L. and Eisenstat, Sarah and Lubiw, Anna and Schulz, Andr\'{e} and Souvaine, Diane L. and Viglietta, Giovanni and Winslow, Andrew}, title = {{Algorithms for Designing Pop-Up Cards}}, booktitle = {30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)}, pages = {269--280}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-50-7}, ISSN = {1868-8969}, year = {2013}, volume = {20}, editor = {Portier, Natacha and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.269}, URN = {urn:nbn:de:0030-drops-39407}, doi = {10.4230/LIPIcs.STACS.2013.269}, annote = {Keywords: geometric folding, linkages, universality} }
Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Erik D. Demaine, Matthew J. Patitz, Robert T. Schweller, and Scott M. Summers. Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor (Extended Abstract). In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 201-212, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
@InProceedings{demaine_et_al:LIPIcs.STACS.2011.201, author = {Demaine, Erik D. and Patitz, Matthew J. and Schweller, Robert T. and Summers, Scott M.}, title = {{Self-Assembly of Arbitrary Shapes Using RNAse Enzymes: Meeting the Kolmogorov Bound with Small Scale Factor}}, booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, pages = {201--212}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-25-5}, ISSN = {1868-8969}, year = {2011}, volume = {9}, editor = {Schwentick, Thomas and D\"{u}rr, Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.201}, URN = {urn:nbn:de:0030-drops-30118}, doi = {10.4230/LIPIcs.STACS.2011.201}, annote = {Keywords: Biomolecular computation, RNAse enzyme self-assembly, algorithmic self-assembly, Komogorov complexity} }
Published in: Dagstuhl Seminar Proceedings, Volume 10091, Data Structures (2010)
Lars Arge, Erik D. Demaine, and Raimund Seidel. 10091 Abstracts Collection – Data Structures. In Data Structures. Dagstuhl Seminar Proceedings, Volume 10091, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{arge_et_al:DagSemProc.10091.1, author = {Arge, Lars and Demaine, Erik D. and Seidel, Raimund}, title = {{10091 Abstracts Collection – Data Structures}}, booktitle = {Data Structures}, pages = {1--16}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10091}, editor = {Lars Arge and Erik D. Demaine and Raimund Seidel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10091.1}, URN = {urn:nbn:de:0030-drops-26864}, doi = {10.4230/DagSemProc.10091.1}, annote = {Keywords: Data structures, information retrieval, complexity, algorithms} }
Published in: Dagstuhl Seminar Proceedings, Volume 9511, Parameterized complexity and approximation algorithms (2010)
Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dániel Marx. 09511 Abstracts Collection – Parameterized complexity and approximation algorithms. In Parameterized complexity and approximation algorithms. Dagstuhl Seminar Proceedings, Volume 9511, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{demaine_et_al:DagSemProc.09511.1, author = {Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Marx, D\'{a}niel}, title = {{09511 Abstracts Collection – Parameterized complexity and approximation algorithms}}, booktitle = {Parameterized complexity and approximation algorithms}, pages = {1--14}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9511}, editor = {Erik D. Demaine and MohammadTaghi Hajiaghayi and D\'{a}niel Marx}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09511.1}, URN = {urn:nbn:de:0030-drops-25025}, doi = {10.4230/DagSemProc.09511.1}, annote = {Keywords: Parameterized complexity, Approximation algorithms} }
Published in: Dagstuhl Seminar Proceedings, Volume 9511, Parameterized complexity and approximation algorithms (2010)
Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dániel Marx. 09511 Executive Summary – Parameterized complexity and approximation algorithms. In Parameterized complexity and approximation algorithms. Dagstuhl Seminar Proceedings, Volume 9511, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{demaine_et_al:DagSemProc.09511.2, author = {Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Marx, D\'{a}niel}, title = {{09511 Executive Summary – Parameterized complexity and approximation algorithms}}, booktitle = {Parameterized complexity and approximation algorithms}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9511}, editor = {Erik D. Demaine and MohammadTaghi Hajiaghayi and D\'{a}niel Marx}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09511.2}, URN = {urn:nbn:de:0030-drops-25011}, doi = {10.4230/DagSemProc.09511.2}, annote = {Keywords: Parameterized complexity, Approximation algorithms} }
Published in: Dagstuhl Seminar Proceedings, Volume 9511, Parameterized complexity and approximation algorithms (2010)
Erik D. Demaine, MohammadTaghi Hajiaghayi, and Dániel Marx. 09511 Open Problems – Parameterized complexity and approximation algorithms. In Parameterized complexity and approximation algorithms. Dagstuhl Seminar Proceedings, Volume 9511, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{demaine_et_al:DagSemProc.09511.3, author = {Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Marx, D\'{a}niel}, title = {{09511 Open Problems – Parameterized complexity and approximation algorithms}}, booktitle = {Parameterized complexity and approximation algorithms}, pages = {1--10}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9511}, editor = {Erik D. Demaine and MohammadTaghi Hajiaghayi and D\'{a}niel Marx}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09511.3}, URN = {urn:nbn:de:0030-drops-24992}, doi = {10.4230/DagSemProc.09511.3}, annote = {Keywords: Parameterized complexity, approximation algorithms, open problems} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Glencora Borradaile, Erik D. Demaine, and Siamak Tazari. Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 171-182, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{borradaile_et_al:LIPIcs.STACS.2009.1835, author = {Borradaile, Glencora and Demaine, Erik D. and Tazari, Siamak}, title = {{Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {171--182}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1835}, URN = {urn:nbn:de:0030-drops-18355}, doi = {10.4230/LIPIcs.STACS.2009.1835}, annote = {Keywords: Polynomial-time approximation scheme, Bounded-genus graph, Embedded graph, Steiner tree, Survivable-network design, Subset TSP} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, and Morteza Zadimoghaddam. The Price of Anarchy in Cooperative Network Creation Games. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 301-312, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{demaine_et_al:LIPIcs.STACS.2009.1839, author = {Demaine, Erik D. and Hajiaghayi, MohammadTaghi and Mahini, Hamid and Zadimoghaddam, Morteza}, title = {{The Price of Anarchy in Cooperative Network Creation Games}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {301--312}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1839}, URN = {urn:nbn:de:0030-drops-18390}, doi = {10.4230/LIPIcs.STACS.2009.1839}, annote = {Keywords: } }
Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)
Erik D. Demaine, Rudolf Fleischer, Avierzi Fraenkel, and Richard Nowakowski. Algorithmic Combinatorial Game Theory (Dagstuhl Seminar 02081). Dagstuhl Seminar Report 334, pp. 1-39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2002)
@TechReport{demaine_et_al:DagSemRep.334, author = {Demaine, Erik D. and Fleischer, Rudolf and Fraenkel, Avierzi and Nowakowski, Richard}, title = {{Algorithmic Combinatorial Game Theory (Dagstuhl Seminar 02081)}}, pages = {1--39}, ISSN = {1619-0203}, year = {2002}, type = {Dagstuhl Seminar Report}, number = {334}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemRep.334}, URN = {urn:nbn:de:0030-drops-152169}, doi = {10.4230/DagSemRep.334}, }
Published in: Dagstuhl Seminar Proceedings, Volume 9111, Computational Geometry (2009)
Daniel Kane, Gregory Nathan Price, and Erik Demaine. A Pseudopolynomial Algorithm for Alexandrov's Theorem. In Computational Geometry. Dagstuhl Seminar Proceedings, Volume 9111, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{kane_et_al:DagSemProc.09111.2, author = {Kane, Daniel and Price, Gregory Nathan and Demaine, Erik}, title = {{A Pseudopolynomial Algorithm for Alexandrov's Theorem}}, booktitle = {Computational Geometry}, pages = {1--22}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2009}, volume = {9111}, editor = {Pankaj Kumar Agarwal and Helmut Alt and Monique Teillaud}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09111.2}, URN = {urn:nbn:de:0030-drops-20328}, doi = {10.4230/DagSemProc.09111.2}, annote = {Keywords: Folding, metrics, pseudopolynomial, algorithms} }
Published in: Dagstuhl Seminar Proceedings, Volume 7281, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007)
Erik Demaine, Gregory Z. Gutin, Daniel Marx, and Ulrike Stege. 07281 Open Problems – Structure Theory and FPT Algorithmcs for Graphs, Digraphs and Hypergraphs. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings, Volume 7281, pp. 1-6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
@InProceedings{demaine_et_al:DagSemProc.07281.2, author = {Demaine, Erik and Gutin, Gregory Z. and Marx, Daniel and Stege, Ulrike}, title = {{07281 Open Problems – Structure Theory and FPT Algorithmcs for Graphs, Digraphs and Hypergraphs}}, booktitle = {Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs}, pages = {1--6}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {7281}, editor = {Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07281.2}, URN = {urn:nbn:de:0030-drops-12542}, doi = {10.4230/DagSemProc.07281.2}, annote = {Keywords: } }
Published in: Dagstuhl Seminar Proceedings, Volume 7281, Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs (2007)
Erik Demaine, Gregory Z. Gutin, Daniel Marx, and Ulrike Stege. 07281 Abstracts Collection – Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. In Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs. Dagstuhl Seminar Proceedings, Volume 7281, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
@InProceedings{demaine_et_al:DagSemProc.07281.1, author = {Demaine, Erik and Gutin, Gregory Z. and Marx, Daniel and Stege, Ulrike}, title = {{07281 Abstracts Collection – Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs}}, booktitle = {Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs}, pages = {1--14}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {7281}, editor = {Erik Demaine and Gregory Z. Gutin and Daniel Marx and Ulrike Stege}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07281.1}, URN = {urn:nbn:de:0030-drops-12450}, doi = {10.4230/DagSemProc.07281.1}, annote = {Keywords: Parameterized complexity, fixed-parameter tractability, graph structure theory} }
Published in: Dagstuhl Seminar Proceedings, Volume 4301, Cache-Oblivious and Cache-Aware Algorithms (2005)
Lars Arge, Michael A. Bender, Erik Demaine, Charles Leiserson, and Kurt Mehlhorn. 04301 Abstracts Collection – Cache-Oblivious and Cache-Aware Algorithms. In Cache-Oblivious and Cache-Aware Algorithms. Dagstuhl Seminar Proceedings, Volume 4301, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)
@InProceedings{arge_et_al:DagSemProc.04301.1, author = {Arge, Lars and Bender, Michael A. and Demaine, Erik and Leiserson, Charles and Mehlhorn, Kurt}, title = {{04301 Abstracts Collection – Cache-Oblivious and Cache-Aware Algorithms}}, booktitle = {Cache-Oblivious and Cache-Aware Algorithms}, pages = {1--14}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2005}, volume = {4301}, editor = {Lars Arge and Michael A. Bender and Erik Demaine and Charles Leiserson and Kurt Mehlhorn}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.04301.1}, URN = {urn:nbn:de:0030-drops-1576}, doi = {10.4230/DagSemProc.04301.1}, annote = {Keywords: Cache oblivious , cache aware , external memory , I/O-efficient algorithms , data structures} }
Feedback for Dagstuhl Publishing