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 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 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Rathish Das, Andrea Lincoln, Jayson Lynch, and J. Ian Munro. Dynamic Boolean Formula Evaluation. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 61:1-61:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{das_et_al:LIPIcs.ISAAC.2021.61, author = {Das, Rathish and Lincoln, Andrea and Lynch, Jayson and Munro, J. Ian}, title = {{Dynamic Boolean Formula Evaluation}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {61:1--61:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.61}, URN = {urn:nbn:de:0030-drops-154945}, doi = {10.4230/LIPIcs.ISAAC.2021.61}, annote = {Keywords: Data Structures, SAT, Dynamic Algorithms, Boolean Formulas, Fine-grained Complexity, Parallel Algorithms} }
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)
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 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} }