13 Search Results for "Chung, Lily"

Document
DOI: 10.4230/LIPIcs.FUN.2026.12
A Bookworm Climbs up the Polynomial Hierarchy: Meta-Restoration Complexity in Arithmetic Puzzles

Authors: Brynmor Chapman, Lily Chung, Erik D. Demaine, Yota Irino, Della Hendrickson, Tonan Kamata, and Ryuhei Uehara

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
In arithmetic puzzles, a partially specified arithmetic expression must be completed to make the computation valid. Arithmetical restoration puzzles require filling in missing digits, while cryptarithms involve assigning digits to letters. The Japanese term mushikui-zan ("bookwormed arithmetic") commonly refers to arithmetical restorations, where we imagine the missing digits have been eaten by a bookworm. Puzzle creator Yousuke Ikeda proposed a new type of puzzle in which a previously designed bookwormed arithmetic with multiplication - known to have a unique solution - has itself been "bookwormed", that is, partially erased. The goal is to restore the specified blanks so that the resulting bookwormed puzzle again has a unique solution. We further generalize this framework: for each k ≥ 2, we define level-k puzzles as those in which type-k blanks must be filled to make the resulting level-(k{-}1) puzzle uniquely solvable. We study the level-k versions of the Boolean satisfiability problem, and show that they form a hierarchy of Σ^P_k-complete decision problems, tightly matching the levels of the polynomial hierarchy. As applications, we show that the level-k arithmetical restoration problem with multiplication is Σ^P_k-complete, as is the level-k cryptarithm problem. On the positive side, we show that level-2 arithmetical restoration puzzles with addition are solvable in polynomial time.
Cite as

Brynmor Chapman, Lily Chung, Erik D. Demaine, Yota Irino, Della Hendrickson, Tonan Kamata, and Ryuhei Uehara. A Bookworm Climbs up the Polynomial Hierarchy: Meta-Restoration Complexity in Arithmetic Puzzles. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 12:1-12:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chapman_et_al:LIPIcs.FUN.2026.12,
  author =	{Chapman, Brynmor and Chung, Lily and Demaine, Erik D. and Irino, Yota and Hendrickson, Della and Kamata, Tonan and Uehara, Ryuhei},
  title =	{{A Bookworm Climbs up the Polynomial Hierarchy: Meta-Restoration Complexity in Arithmetic Puzzles}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{12:1--12:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.12},
  URN =		{urn:nbn:de:0030-drops-257311},
  doi =		{10.4230/LIPIcs.FUN.2026.12},
  annote =	{Keywords: arithmetical restoration, cryptarithms, polynomial hierarchy, uniqueness quantifier, puzzle complexity}
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.32
Tetris Is Hard with Just One Piece Type

Authors: MIT Hardness Group, Josh Brunner, Erik D. Demaine, Della Hendrickson, and Jeffery Li

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
We analyze the computational complexity of Tetris clearing (determining whether the player can clear an initial board using a given sequence of pieces) and survival (determining whether the player can avoid losing before placing all the given pieces in an initial board) when restricted to a single polyomino piece type. We prove, for any tetromino piece type P except for O, the NP-hardness of Tetris clearing and survival under the standard Super Rotation System (SRS), even when the input sequence consists of only a specified number of P pieces. These surprising results disprove a 23-year-old conjecture on the computational complexity of Tetris with only I pieces (although our result is only for a specific rotation system). As a corollary, we prove the NP-hardness of Tetris clearing when the sequence of pieces has to be able to be generated from a 7k-bag randomizer for any positive integer k ≥ 1. On the positive side, we give polynomial-time algorithms for Tetris clearing and survival when the input sequence consists of only dominoes, assuming a particular rotation model, solving a version of a 9-year-old open problem. Along the way, we give polynomial-time algorithms for Tetris clearing and survival with 1 × k pieces (for any fixed k), provided the top k-1 rows are initially empty, showing that our I NP-hardness result needs to have filled cells in the top three rows.
Cite as

MIT Hardness Group, Josh Brunner, Erik D. Demaine, Della Hendrickson, and Jeffery Li. Tetris Is Hard with Just One Piece Type. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 32:1-32:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{mithardnessgroup_et_al:LIPIcs.FUN.2026.32,
  author =	{MIT Hardness Group and Brunner, Josh and Demaine, Erik D. and Hendrickson, Della and Li, Jeffery},
  title =	{{Tetris Is Hard with Just One Piece Type}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{32:1--32:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.32},
  URN =		{urn:nbn:de:0030-drops-257515},
  doi =		{10.4230/LIPIcs.FUN.2026.32},
  annote =	{Keywords: complexity, hardness, video games, counting}
}
Document
DOI: 10.4230/LIPIcs.FUN.2026.40
An ASP-Completeness Framework for Dynasty Puzzles

Authors: Kosuke Susukita

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
A certain class of pencil-and-paper puzzles shares common rules: given a grid, certain cells must be shaded such that i) no two shaded cells are orthogonally adjacent, and ii) all unshaded cells are orthogonally connected. Such puzzles are sometimes referred to as "dynasty puzzles" within parts of the online puzzle community. We introduce a framework for proving the ASP-completeness (i.e., NP-complete under parsimonious reductions) of various dynasty puzzles. We apply this framework to seven specific dynasty puzzles - Akichiwake, Aquapelago, Ayeheya, Guide Arrow, Heyawake, Hitori, and Kurodoko. As a consequence, for given k solutions of any of these puzzles, deciding whether a distinct solution exists is NP-complete, and counting the number of solutions is #P-complete. Our results strengthen the known result of ASP-completeness for Heyawake and establish the ASP-completeness of the other six puzzles. The main idea is to reconstruct the reduction from the Tree-Residue Vertex-Breaking Problem (TRVB) to the Hamiltonian Cycle Problem introduced by MIT Hardness Group (2024). In our framework, the connectivity of the unshaded cells ensures the connectivity of the shaded cells, allowing the shaded cells to simulate TRVB, which is also an alternative representation of the Hamiltonian cycles under certain conditions.
Cite as

Kosuke Susukita. An ASP-Completeness Framework for Dynasty Puzzles. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 40:1-40:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{susukita:LIPIcs.FUN.2026.40,
  author =	{Susukita, Kosuke},
  title =	{{An ASP-Completeness Framework for Dynasty Puzzles}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{40:1--40:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.40},
  URN =		{urn:nbn:de:0030-drops-257596},
  doi =		{10.4230/LIPIcs.FUN.2026.40},
  annote =	{Keywords: ASP-completeness, pencil-and-paper puzzles, dynasty puzzles, Hitori, Kurodoko, Hamiltonian cycle, Tree-Residue Vertex-Breaking}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.1
Reconfiguration of Unit Squares and Disks: PSPACE-Hardness in Simple Settings

Authors: Mikkel Abrahamsen, Kevin Buchin, Maike Buchin, Linda Kleist, Maarten Löffler, Lena Schlipf, André Schulz, and Jack Stade

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We study well-known reconfiguration problems. Given a start and a target configuration of geometric objects in a polygon, we wonder whether we can move the objects from the start configuration to the target configuration while avoiding collisions between the objects and staying within the polygon. Problems of this type have been considered since the early 80s by roboticists and computational geometers. In this paper, we study some of the simplest possible variants where the objects are labeled or unlabeled unit squares or unit disks. In unlabeled reconfiguration, the objects are identical, so that any object is allowed to end at any of the targets positions. In the labeled variant, each object has a designated target position. The results for the labeled variants are direct consequences from our insights on the unlabeled versions. We show that it is PSPACE-hard to decide whether there exists a reconfiguration of (unlabeled/labeled) unit squares even in a simple polygon. Previously, it was only known to be PSPACE-hard in a polygon with holes for both the unlabeled and labeled version [Solovey and Halperin, Int. J. Robotics Res. 2016]. Our proof is based on a result of independent interest, namely that reconfiguration between two satisfying assignments of a formula of Monotone-Planar-3-Sat is also PSPACE-complete. The reduction from reconfiguration of Monotone-Planar-3-Sat to reconfiguration of unit squares extends techniques recently developed to show NP-hardness of packing unit squares in a simple polygon [Abrahamsen and Stade, FOCS 2024]. We also show PSPACE-hardness of reconfiguration of (unlabeled/labeled) unit disks in a polygon with holes. Previously, it was known that unlabeled reconfiguration of disks of two different sizes was PSPACE-hard [Brocken, van der Heijden, Kostitsyna, Lo-Wong and Surtel, FUN 2021].
Cite as

Mikkel Abrahamsen, Kevin Buchin, Maike Buchin, Linda Kleist, Maarten Löffler, Lena Schlipf, André Schulz, and Jack Stade. Reconfiguration of Unit Squares and Disks: PSPACE-Hardness in Simple Settings. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{abrahamsen_et_al:LIPIcs.SoCG.2025.1,
  author =	{Abrahamsen, Mikkel and Buchin, Kevin and Buchin, Maike and Kleist, Linda and L\"{o}ffler, Maarten and Schlipf, Lena and Schulz, Andr\'{e} and Stade, Jack},
  title =	{{Reconfiguration of Unit Squares and Disks: PSPACE-Hardness in Simple Settings}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{1:1--1:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.1},
  URN =		{urn:nbn:de:0030-drops-231539},
  doi =		{10.4230/LIPIcs.SoCG.2025.1},
  annote =	{Keywords: reconfiguration, unit square, unit disk, unlabeled, labeled, simple polygon, polygon}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.5
Optimal Motion Planning for Two Square Robots in a Rectilinear Environment

Authors: Pankaj K. Agarwal, Mark de Berg, Benjamin Holmgren, Alex Steiger, and Martijn Struijs

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
Let W ⊂ ℝ² be a rectilinear polygonal environment (that is, a rectilinear polygon potentially with holes) with a total of n vertices, and let A,B be two robots, each modeled as an axis-aligned unit square, that can move rectilinearly inside W. The goal is to compute an optimal collision-free motion plan π for A and B between a given pair of source and target configurations. We study two variants of this problem and obtain the following results. - Min-Sum: Here the goal is to compute a motion plan that minimizes the sum of the lengths of the paths of the robots. We present an O(n⁴log n)-time algorithm for computing an optimal solution to the min-sum problem. This is the first polynomial-time algorithm to compute an optimal, collision-free motion of two robots amid obstacles in a planar polygonal environment. - Min-Makespan: Here the robots can move with at most unit speed, and the goal is to compute a motion plan that minimizes the maximum time taken by a robot to reach its target location. We prove that the min-makespan variant is NP-hard.
Cite as

Pankaj K. Agarwal, Mark de Berg, Benjamin Holmgren, Alex Steiger, and Martijn Struijs. Optimal Motion Planning for Two Square Robots in a Rectilinear Environment. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{agarwal_et_al:LIPIcs.SoCG.2025.5,
  author =	{Agarwal, Pankaj K. and de Berg, Mark and Holmgren, Benjamin and Steiger, Alex and Struijs, Martijn},
  title =	{{Optimal Motion Planning for Two Square Robots in a Rectilinear Environment}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{5:1--5:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.5},
  URN =		{urn:nbn:de:0030-drops-231577},
  doi =		{10.4230/LIPIcs.SoCG.2025.5},
  annote =	{Keywords: Computational geometry, motion planning, multiple robots, rectilinear paths}
}
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
Academic Track
DOI: 10.4230/OASIcs.SAIA.2024.1
On Assessing ML Model Robustness: A Methodological Framework (Academic Track)

Authors: Afef Awadid and Boris Robert

Published in: OASIcs, Volume 126, Symposium on Scaling AI Assessments (SAIA 2024)

Abstract
Due to their uncertainty and vulnerability to adversarial attacks, machine learning (ML) models can lead to severe consequences, including the loss of human life, when embedded in safety-critical systems such as autonomous vehicles. Therefore, it is crucial to assess the empirical robustness of such models before integrating them into these systems. ML model robustness refers to the ability of an ML model to be insensitive to input perturbations and maintain its performance. Against this background, the Confiance.ai research program proposes a methodological framework for assessing the empirical robustness of ML models. The framework encompasses methodological processes (guidelines) captured in Capella models, along with a set of supporting tools. This paper aims to provide an overview of this framework and its application in an industrial setting.
Cite as

Afef Awadid and Boris Robert. On Assessing ML Model Robustness: A Methodological Framework (Academic Track). In Symposium on Scaling AI Assessments (SAIA 2024). Open Access Series in Informatics (OASIcs), Volume 126, pp. 1:1-1:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{awadid_et_al:OASIcs.SAIA.2024.1,
  author =	{Awadid, Afef and Robert, Boris},
  title =	{{On Assessing ML Model Robustness: A Methodological Framework}},
  booktitle =	{Symposium on Scaling AI Assessments (SAIA 2024)},
  pages =	{1:1--1:10},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-357-7},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{126},
  editor =	{G\"{o}rge, Rebekka and Haedecke, Elena and Poretschkin, Maximilian and Schmitz, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SAIA.2024.1},
  URN =		{urn:nbn:de:0030-drops-227410},
  doi =		{10.4230/OASIcs.SAIA.2024.1},
  annote =	{Keywords: ML model robustness, assessment, framework, methodological processes, tools}
}
Document
DOI: 10.4230/LIPIcs.FUN.2024.23
ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles

Authors: MIT Hardness Group, Josh Brunner, Lily Chung, Erik D. Demaine, Della Hendrickson, and Andy Tockman

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract
We prove that Hamiltonicity in maximum-degree-3 grid graphs (directed or undirected) is ASP-complete, i.e., it has a parsimonious reduction from every NP search problem (including a polynomial-time bijection between solutions). As a consequence, given k Hamiltonian cycles, it is NP-complete to find another; and counting Hamiltonian cycles is #P-complete. If we require the grid graph’s vertices to form a full m × n rectangle, then we show that Hamiltonicity remains ASP-complete if the edges are directed or if we allow removing some edges (whereas including all undirected edges is known to be easy). These results enable us to develop a stronger "T-metacell" framework for proving ASP-completeness of rectangular puzzles, which requires building just a single gadget representing a degree-3 grid-graph vertex. We apply this general theory to prove ASP-completeness of 37 pencil-and-paper puzzles where the goal is to draw a loop subject to given constraints: Slalom, Onsen-meguri, Mejilink, Detour, Tapa-Like Loop, Kouchoku, Icelom; Masyu, Yajilin, Nagareru, Castle Wall, Moon or Sun, Country Road, Geradeweg, Maxi Loop, Mid-loop, Balance Loop, Simple Loop, Haisu, Reflect Link, Linesweeper; Vertex/Touch Slitherlink, Dotchi-Loop, Ovotovata, Building Walk, Rail Pool, Disorderly Loop, Ant Mill, Koburin, Mukkonn Enn, Rassi Silai, (Crossing) Ichimaga, Tapa, Canal View, and Aqre. The last 13 of these puzzles were not even known to be NP-hard. Along the way, we prove ASP-completeness of some simple forms of Tree-Residue Vertex-Breaking (TRVB), including planar multigraphs with degree-6 breakable vertices, or with degree-4 breakable and degree-1 unbreakable vertices.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.42
Improved Local Computation Algorithms for Constructing Spanners

Authors: Rubi Arviv, Lily Chung, Reut Levi, and Edward Pyne

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

Abstract
A spanner of a graph is a subgraph that preserves lengths of shortest paths up to a multiplicative distortion. For every k, a spanner with size O(n^{1+1/k}) and stretch (2k+1) can be constructed by a simple centralized greedy algorithm, and this is tight assuming Erdős girth conjecture. In this paper we study the problem of constructing spanners in a local manner, specifically in the Local Computation Model proposed by Rubinfeld et al. (ICS 2011). We provide a randomized Local Computation Agorithm (LCA) for constructing (2r-1)-spanners with Õ(n^{1+1/r}) edges and probe complexity of Õ(n^{1-1/r}) for r ∈ {2,3}, where n denotes the number of vertices in the input graph. Up to polylogarithmic factors, in both cases, the stretch factor is optimal (for the respective number of edges). In addition, our probe complexity for r = 2, i.e., for constructing a 3-spanner, is optimal up to polylogarithmic factors. Our result improves over the probe complexity of Parter et al. (ITCS 2019) that is Õ(n^{1-1/2r}) for r ∈ {2,3}. Both our algorithms and the algorithms of Parter et al. use a combination of neighbor-probes and pair-probes in the above-mentioned LCAs. For general k ≥ 1, we provide an LCA for constructing O(k²)-spanners with Õ(n^{1+1/k}) edges using O(n^{2/3}Δ²) neighbor-probes, improving over the Õ(n^{2/3}Δ⁴) algorithm of Parter et al. By developing a new randomized LCA for graph decomposition, we further improve the probe complexity of the latter task to be O(n^{2/3-(1.5-α)/k}Δ²), for any constant α > 0. This latter LCA may be of independent interest.
Cite as

Rubi Arviv, Lily Chung, Reut Levi, and Edward Pyne. Improved Local Computation Algorithms for Constructing Spanners. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 42:1-42:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{arviv_et_al:LIPIcs.APPROX/RANDOM.2023.42,
  author =	{Arviv, Rubi and Chung, Lily and Levi, Reut and Pyne, Edward},
  title =	{{Improved Local Computation Algorithms for Constructing Spanners}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{42:1--42:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.42},
  URN =		{urn:nbn:de:0030-drops-188671},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.42},
  annote =	{Keywords: Local Computation Algorithms, Spanners}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2022.32
Lower Bounds on Retroactive Data Structures

Authors: Lily Chung, Erik D. Demaine, Dylan Hendrickson, and Jayson Lynch

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

Abstract
We prove essentially optimal fine-grained lower bounds on the gap between a data structure and a partially retroactive version of the same data structure. Precisely, assuming any one of three standard conjectures, we describe a problem that has a data structure where operations run in O(T(n,m)) time per operation, but any partially retroactive version of that data structure requires T(n,m)⋅m^{1-o(1)} worst-case time per operation, where n is the size of the data structure at any time and m is the number of operations. Any data structure with operations running in O(T(n,m)) time per operation can be converted (via the "rollback method") into a partially retroactive data structure running in O(T(n,m)⋅m) time per operation, so our lower bound is tight up to an m^o(1) factor common in fine-grained complexity.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.29
Flat Folding an Unassigned Single-Vertex Complex (Combinatorially Embedded Planar Graph with Specified Edge Lengths) Without Flat Angles

Authors: Lily Chung, Erik D. Demaine, Dylan Hendrickson, and Victor Luo

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
A foundational result in origami mathematics is Kawasaki and Justin’s simple, efficient characterization of flat foldability for unassigned single-vertex crease patterns (where each crease can fold mountain or valley) on flat material. This result was later generalized to cones of material, where the angles glued at the single vertex may not sum to 360^∘. Here we generalize these results to when the material forms a complex (instead of a manifold), and thus the angles are glued at the single vertex in the structure of an arbitrary planar graph (instead of a cycle). Like the earlier characterizations, we require all creases to fold mountain or valley, not remain unfolded flat; otherwise, the problem is known to be NP-complete (weakly for flat material and strongly for complexes). Equivalently, we efficiently characterize which combinatorially embedded planar graphs with prescribed edge lengths can fold flat, when all angles must be mountain or valley (not unfolded flat). Our algorithm runs in O(n log³ n) time, improving on the previous best algorithm of O(n² log n).
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
DOI: 10.4230/LIPIcs.FUN.2022.3
Pushing Blocks via Checkable Gadgets: PSPACE-Completeness of Push-1F and Block/Box Dude

Authors: Joshua Ani, Lily Chung, Erik D. Demaine, Yevhenii Diomidov, Dylan Hendrickson, and Jayson Lynch

Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)

Abstract
We prove PSPACE-completeness of the well-studied pushing-block puzzle Push-1F, a theoretical abstraction of many video games (first posed in 1999). We also prove PSPACE-completeness of two versions of the recently studied block-moving puzzle game with gravity, Block Dude - a video game dating back to 1994 - featuring either liftable blocks or pushable blocks. Two of our reductions are built on a new framework for "checkable" gadgets, extending the motion-planning-through-gadgets framework to support gadgets that can be misused, provided those misuses can be detected later.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.7
1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete

Authors: Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
Consider n²-1 unit-square blocks in an n × n square board, where each block is labeled as movable horizontally (only), movable vertically (only), or immovable - a variation of Rush Hour with only 1 × 1 cars and fixed blocks. We prove that it is PSPACE-complete to decide whether a given block can reach the left edge of the board, by reduction from Nondeterministic Constraint Logic via 2-color oriented Subway Shuffle. By contrast, polynomial-time algorithms are known for deciding whether a given block can be moved by one space, or when each block either is immovable or can move both horizontally and vertically. Our result answers a 15-year-old open problem by Tromp and Cilibrasi, and strengthens previous PSPACE-completeness results for Rush Hour with vertical 1 × 2 and horizontal 2 × 1 movable blocks and 4-color Subway Shuffle.
Cite as

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)

Copy BibTex To Clipboard

@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}
}
  • Refine by Type
  • 13 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 3 2026
  • 4 2025
  • 1 2024
  • 1 2023
  • 3 2022
  • Show More...

  • Refine by Author
  • 8 Demaine, Erik D.
  • 7 Chung, Lily
  • 4 Hendrickson, Dylan
  • 3 Brunner, Josh
  • 3 Hendrickson, Della
  • Show More...

  • Refine by Series/Journal
  • 12 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 6 Theory of computation → Problems, reductions and completeness
  • 2 Theory of computation → Complexity classes
  • 2 Theory of computation → Computational geometry
  • 1 Mathematics of computing → Graph algorithms
  • 1 Software and its engineering → Software verification and validation
  • Show More...

  • Refine by Keyword
  • 2 motion planning
  • 2 pencil-and-paper puzzles
  • 1 ASP-completeness
  • 1 Computational geometry
  • 1 Gadgets
  • Show More...

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-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact