Search Results

Documents authored by Diomidova, Jenny

Document
DOI: 10.4230/LIPIcs.SAND.2025.11
Hardness of Traversing Gadget Systems with Small Bandwidth

Authors: MIT Gadgets Group, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Markus Hecher, and Jayson Lynch

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
The motion-planning-through-gadgets framework has enabled proofs of PSPACE-completeness for many motion-planning problems, ranging from swarm and modular robotics to DNA computing to video games. In this paper, we strengthen this framework to show that, for several useful gadgets and gadget families, motion planning remains PSPACE-complete even when gadgets are connected together into a graph of constant bandwidth (which implies constant pathwidth, treewidth, and cliquewidth). We then show how this result applies to several geometric/grid-based motion-planning problems, establishing PSPACE-completeness even when restricted to a rectangle/box where only one dimension is large (superconstant). On the positive side, we find one family of gadgets (DAG gadgets) for which motion planning is fixed-parameter tractable with respect to bandwidth.
Cite as

MIT Gadgets Group, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Markus Hecher, and Jayson Lynch. Hardness of Traversing Gadget Systems with Small Bandwidth. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mitgadgetsgroup_et_al:LIPIcs.SAND.2025.11,
  author =	{MIT Gadgets Group and Demaine, Erik D. and Diomidova, Jenny and Gomez, Timothy and Hecher, Markus and Lynch, Jayson},
  title =	{{Hardness of Traversing Gadget Systems with Small Bandwidth}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.11},
  URN =		{urn:nbn:de:0030-drops-230648},
  doi =		{10.4230/LIPIcs.SAND.2025.11},
  annote =	{Keywords: Gadgets, Motion Planning, Parameterized Complexity, Hardness}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2024.51
Easier Ways to Prove Counting Hard: A Dichotomy for Generalized #SAT, Applied to Constraint Graphs

Authors: MIT Hardness Group, Josh Brunner, Erik D. Demaine, Jenny Diomidova, Timothy Gomez, Markus Hecher, Frederick Stock, and Zixiang Zhou

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
To prove #P-hardness, a single-call reduction from #2SAT needs a clause gadget to have exactly the same number of solutions for all satisfying assignments - no matter how many and which literals satisfy the clause. In this paper, we relax this condition, making it easier to find #P-hardness reductions. Specifically, we introduce a framework called Generalized #SAT where each clause contributes a term to the total count of solutions based on a given function of the literals. For two-variable clauses (a natural generalization of #2SAT), we prove a dichotomy theorem characterizing when Generalized #SAT is in FP versus #P-complete. Equipped with these tools, we analyze the complexity of counting solutions to Constraint Graph Satisfiability (CGS), a framework previously used to prove NP-hardness (and PSPACE-hardness) of many puzzles and games. We prove CGS ASP-hard, meaning that there is a parsimonious reduction (with algorithmic bijection on solutions) from every NP search problem, which implies #P-completeness. Then we analyze CGS restricted to various subsets of features (vertex and edge types), and prove most of them either easy (in FP) or hard (#P-complete). Most of our results also apply to planar constraint graphs. CGS is thus a second powerful framework for proving problems #P-hard, with reductions requiring very few gadgets.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.34
Reconfiguration Algorithms for Cubic Modular Robots with Realistic Movement Constraints

Authors: MIT-NASA Space Robots Team, Josh Brunner, Kenneth C. Cheung, Erik D. Demaine, Jenny Diomidova, Christine Gregg, Della H. Hendrickson, and Irina Kostitsyna

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
We introduce and analyze a model for self-reconfigurable robots made up of unit-cube modules. Compared to past models, our model aims to newly capture two important practical aspects of real-world robots. First, modules often do not occupy an exact unit cube, but rather have features like bumps extending outside the allotted space so that modules can interlock. Thus, for example, our model forbids modules from squeezing in between two other modules that are one unit distance apart. Second, our model captures the practical scenario of many passive modules assembled by a single robot, instead of requiring all modules to be able to move on their own. We prove two universality results. First, with a supply of auxiliary modules, we show that any connected polycube structure can be constructed by a carefully aligned plane sweep. Second, without additional modules, we show how to construct any structure for which a natural notion of external feature size is at least a constant; this property largely consolidates forbidden-pattern properties used in previous works on reconfigurable modular robots.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
DOI: 10.4230/LIPIcs.DNA.29.10
Complexity of Reconfiguration in Surface Chemical Reaction Networks

Authors: 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

Published in: LIPIcs, Volume 276, 29th International Conference on DNA Computing and Molecular Programming (DNA 29) (2023)

Abstract
We analyze the computational complexity of basic reconfiguration problems for the recently introduced surface Chemical Reaction Networks (sCRNs), where ordered pairs of adjacent species nondeterministically transform into a different ordered pair of species according to a predefined set of allowed transition rules (chemical reactions). In particular, two questions that are fundamental to the simulation of sCRNs are whether a given configuration of molecules can ever transform into another given configuration, and whether a given cell can ever contain a given species, given a set of transition rules. We show that these problems can be solved in polynomial time, are NP-complete, or are PSPACE-complete in a variety of different settings, including when adjacent species just swap instead of arbitrary transformation (swap sCRNs), and when cells can change species a limited number of times (k-burnout). Most problems turn out to be at least NP-hard except with very few distinct species (2 or 3).
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact