18 Search Results for "Becker, Aaron T."

Document
DOI: 10.4230/LIPIcs.ITCS.2026.14
General Computation Using Slidable Tiles with Deterministic Global Forces

Authors: Alberto Avila-Jimenez, David Barreda, Sarah-Laurie Evans, Austin Luchsinger, Aiden Massie, Robert Schweller, Evan Tomai, and Tim Wylie

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We study the computational power of the Full-Tilt model of motion planning, where slidable polyominos are moved maximally around a board by way of a sequence of directional "tilts." We focus on the deterministic scenario in which the tilts constitute a repeated clockwise rotation. We show that general-purpose computation is possible within this framework by providing a direct and efficient simulation of space-bounded Turing machines in which one computational step of the machine is simulated per O(1) rotations. We further show that the initial tape of the machine can be programmed by an initial tilt-sequence preceding the rotations. This result immediately implies new PSPACE-completeness results for the well-studied problems of occupancy (deciding if a given board location can be occupied by a tile), vacancy (deciding if a location can be emptied), relocation (deciding if a tile can be moved from one location to another), and reconfiguration (can a given board configuration be reconfigured into a second given configuration) that hold even for deterministically repeating tilt cycles such as rotations. All of our PSPACE-completeness results hold even when there is only a single domino in the system beyond singleton tiles. Following, we show that these results work in the Single-Step tilt model for larger constant cycles. We then investigate computational efficiency by showing a modification to implement a two-tape Turing machine in the Full-Tilt model and Systolic Arrays in the Single-Step model. Finally, we show a cyclic implementation for tilt-efficient Threshold Circuits.
Cite as

Alberto Avila-Jimenez, David Barreda, Sarah-Laurie Evans, Austin Luchsinger, Aiden Massie, Robert Schweller, Evan Tomai, and Tim Wylie. General Computation Using Slidable Tiles with Deterministic Global Forces. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 14:1-14:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{avilajimenez_et_al:LIPIcs.ITCS.2026.14,
  author =	{Avila-Jimenez, Alberto and Barreda, David and Evans, Sarah-Laurie and Luchsinger, Austin and Massie, Aiden and Schweller, Robert and Tomai, Evan and Wylie, Tim},
  title =	{{General Computation Using Slidable Tiles with Deterministic Global Forces}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{14:1--14:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.14},
  URN =		{urn:nbn:de:0030-drops-253019},
  doi =		{10.4230/LIPIcs.ITCS.2026.14},
  annote =	{Keywords: motion planning, global control, external forces, deterministic computation, occupancy, vacancy}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.28
Sliding Squares in Parallel

Authors: Hugo A. Akitaya, Sándor P. Fekete, Peter Kramer, Saba Molaei, Christian Rieck, Frederick Stock, and Tobias Wallner

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We consider algorithmic problems motivated by modular robotic reconfiguration in the sliding square model, in which we are given n square-shaped modules in a (labeled or unlabeled) start configuration and need to find a schedule of sliding moves to transform it into a desired goal configuration, maintaining connectivity of the configuration at all times. Recent work has aimed at minimizing the total number of moves, resulting in fully sequential schedules that can perform reconfiguration in 𝒪(n²) moves, or 𝒪(nP) for arrangements of bounding box perimeter size P. We provide first results in the sliding square model that exploit parallel motion, performing reconfiguration in worst-case optimal makespan of 𝒪(P). We also provide tight bounds on the complexity of the problem by showing that even deciding the possibility of reconfiguration within makespan 1 is NP-complete in the unlabeled case. In the labeled variant, we note that deciding the same for makespan 2 is NP-complete, while makespan 1 is straightforward.
Cite as

Hugo A. Akitaya, Sándor P. Fekete, Peter Kramer, Saba Molaei, Christian Rieck, Frederick Stock, and Tobias Wallner. Sliding Squares in Parallel. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 28:1-28:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.ESA.2025.28,
  author =	{A. Akitaya, Hugo and Fekete, S\'{a}ndor P. and Kramer, Peter and Molaei, Saba and Rieck, Christian and Stock, Frederick and Wallner, Tobias},
  title =	{{Sliding Squares in Parallel}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{28:1--28:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.28},
  URN =		{urn:nbn:de:0030-drops-244961},
  doi =		{10.4230/LIPIcs.ESA.2025.28},
  annote =	{Keywords: Sliding squares, parallel motion, reconfigurability, motion planning, multi-agent path finding, makespan, swarm robotics, computational geometry}
}
Document
DOI: 10.4230/OASIcs.SpaceCHI.2025.32
Virtual Reality Prototyping Environment for Concurrent Design, Training and Rover Operations

Authors: Pinar Dogru, Hanjo Schnellbächer, Tarek Can Battikh, and Kristina Remić

Published in: OASIcs, Volume 130, Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)

Abstract
As part of the CASIMAR (Collaborative Astronaut Supporting Interregional Moon Analog Rover) project, initiated by the BVSR e.V. (Bundesverband Studentischer Raumfahrt), the TUDSaT (TU Darmstadt Space Technology e.V.) team is developing a Virtual Reality (VR) prototype environment to support the interdisciplinary design process of lunar exploration technologies. Given the complexity of collaboration among eight organizations, this tool aims to streamline design integration and enhance mission planning. The primary objective is to create a comprehensive 3D model of the rover, complete with predefined procedures and activities, to simulate astronaut-robot interaction. By leveraging VR technology, astronauts can familiarize themselves with the rover and its EVA (Extravehicular Activity) tools before actual deployment, improving operational safety and efficiency. Beyond training applications, this virtual environment serves as a critical platform for designing, testing, and benchmarking rover functionalities and EVA procedures. Ultimately, our work contributes to optimizing human-robotic interaction, ensuring that lunar exploration missions are both effective and well-prepared before reaching the Moon.
Cite as

Pinar Dogru, Hanjo Schnellbächer, Tarek Can Battikh, and Kristina Remić. Virtual Reality Prototyping Environment for Concurrent Design, Training and Rover Operations. In Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025). Open Access Series in Informatics (OASIcs), Volume 130, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dogru_et_al:OASIcs.SpaceCHI.2025.32,
  author =	{Dogru, Pinar and Schnellb\"{a}cher, Hanjo and Battikh, Tarek Can and Remi\'{c}, Kristina},
  title =	{{Virtual Reality Prototyping Environment for Concurrent Design, Training and Rover Operations}},
  booktitle =	{Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)},
  pages =	{32:1--32:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-384-3},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{130},
  editor =	{Bensch, Leonie and Nilsson, Tommy and Nisser, Martin and Pataranutaporn, Pat and Schmidt, Albrecht and Sumini, Valentina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SpaceCHI.2025.32},
  URN =		{urn:nbn:de:0030-drops-240226},
  doi =		{10.4230/OASIcs.SpaceCHI.2025.32},
  annote =	{Keywords: virtual reality (VR), digital twin, human-robot-interaction (HRI), LUNA analog facility, rover, extravehicular activities (EVA), gamification, simulation, user-centered design (UCD), concurrent engineering (CE), space system engineering}
}
Document
DOI: 10.4230/OASIcs.SpaceCHI.2025.26
Movement in Low Gravity (MoLo) – LUNA: Biomechanical Modelling to Mitigate Lunar Surface Operation Risks

Authors: David Andrew Green

Published in: OASIcs, Volume 130, Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)

Abstract
The Artemis programme seeks to develop and test concepts, hardware and approaches to support long term habitation of the Lunar surface, and future missions to Mars. In preparation for the Artemis missions determination of tasks to be performed, the functional requirements of such tasks and as mission duration extends whether physiological deconditioning becomes functionally significant, compromising the crew member’s ability to perform critical tasks on the surface, and/or upon return to earth [MoLo-LUNA – leveraging the Molo programme (and several other activities) - could become a key supporting activity for LUNA incl. validation of the Puppeteer offloading system itself via creation of a complementary MoLo-LUNA-LAB. Furthermore, the MoLo-LUNA programme could become a key facilitator of simulator suit instrumentation/definition, broader astronaut training activities and mission architecture development – including Artemis mission simulations. By employing a Puppeteer system external to the LUNA chamber hall it will optimise utilisation and cost-effectiveness of LUNA, and as such represents a critical service to future LUNA stakeholders. Furthermore, MoLo-LUNA would generate a unique data set that can be leveraged to predict de-conditioning on the Lunar surface - and thereby optimise functionality, and minimise mission risk – including informing the need for, and prescription of exercise countermeasures on the Lunar Surface and in transit. Thus, MoLo-LUNA offers a unique opportunity to place LUNA, and ESA as a key ongoing provider of evidence to define, optimise and support crew Artemis surface missions.
Cite as

David Andrew Green. Movement in Low Gravity (MoLo) – LUNA: Biomechanical Modelling to Mitigate Lunar Surface Operation Risks. In Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025). Open Access Series in Informatics (OASIcs), Volume 130, pp. 26:1-26:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{green:OASIcs.SpaceCHI.2025.26,
  author =	{Green, David Andrew},
  title =	{{Movement in Low Gravity (MoLo) – LUNA: Biomechanical Modelling to Mitigate Lunar Surface Operation Risks}},
  booktitle =	{Advancing Human-Computer Interaction for Space Exploration (SpaceCHI 2025)},
  pages =	{26:1--26:11},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-384-3},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{130},
  editor =	{Bensch, Leonie and Nilsson, Tommy and Nisser, Martin and Pataranutaporn, Pat and Schmidt, Albrecht and Sumini, Valentina},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SpaceCHI.2025.26},
  URN =		{urn:nbn:de:0030-drops-240166},
  doi =		{10.4230/OASIcs.SpaceCHI.2025.26},
  annote =	{Keywords: Locomotion, hypogravity, modelling, Lunar}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.35
Fooling Near-Maximal Decision Trees

Authors: William M. Hoza and Zelin Lv

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

Abstract
For any constant α > 0, we construct an explicit pseudorandom generator (PRG) that fools n-variate decision trees of size m with error ε and seed length (1 + α) ⋅ log₂ m + O(log(1/ε) + log log n). For context, one can achieve seed length (2 + o(1)) ⋅ log₂ m + O(log(1/ε) + log log n) using well-known constructions and analyses of small-bias distributions, but such a seed length is trivial when m ≥ 2^{n/2}. Our approach is to develop a new variant of the classic concept of almost k-wise independence, which might be of independent interest. We say that a distribution X over {0, 1}ⁿ is k-wise ε-probably uniform if every Boolean function f that depends on only k variables satisfies 𝔼[f(X)] ≥ (1 - ε) ⋅ 𝔼[f]. We show how to sample a k-wise ε-probably uniform distribution using a seed of length (1 + α) ⋅ k + O(log(1/ε) + log log n). Meanwhile, we also show how to construct a set H ⊆ 𝔽₂ⁿ such that every feasible system of k linear equations in n variables over 𝔽₂ has a solution in H. The cardinality of H and the time complexity of enumerating H are at most 2^{k + o(k) + polylog n}, whereas small-bias distributions would give a bound of 2^{2k + O(log(n/k))}. By combining our new constructions with work by Chen and Kabanets (TCS 2016), we obtain nontrivial PRGs and hitting sets for linear-size Boolean circuits. Specifically, we get an explicit PRG with seed length (1 - Ω(1)) ⋅ n that fools circuits of size 2.99 ⋅ n over the U₂ basis, and we get a hitting set with time complexity 2^{(1 - Ω(1)) ⋅ n} for circuits of size 2.49 ⋅ n over the B₂ basis.
Cite as

William M. Hoza and Zelin Lv. Fooling Near-Maximal Decision Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 35:1-35:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hoza_et_al:LIPIcs.APPROX/RANDOM.2025.35,
  author =	{Hoza, William M. and Lv, Zelin},
  title =	{{Fooling Near-Maximal Decision Trees}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{35:1--35:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.35},
  URN =		{urn:nbn:de:0030-drops-244019},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.35},
  annote =	{Keywords: almost k-wise independence, decision trees, pseudorandom generators}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.8
Multipass Linear Sketches for Geometric LP-Type Problems

Authors: N. Efe Çekirge, William Gay, and David P. Woodruff

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

Abstract
LP-type problems such as the Minimum Enclosing Ball (MEB), Linear Support Vector Machine (SVM), Linear Programming (LP), and Semidefinite Programming (SDP) are fundamental combinatorial optimization problems, with many important applications in machine learning applications such as classification, bioinformatics, and noisy learning. We study LP-type problems in several streaming and distributed big data models, giving ε-approximation linear sketching algorithms with a focus on the high accuracy regime with low dimensionality d, that is, when d < (1/ε)^0.999. Our main result is an O(ds) pass algorithm with O(s(√d/ε)^{3d/s}) ⋅ poly(d, log (1/ε)) space complexity in words, for any parameter s ∈ [1, d log (1/ε)], to solve ε-approximate LP-type problems of O(d) combinatorial and VC dimension. Notably, by taking s = d log (1/ε), we achieve space complexity polynomial in d and polylogarithmic in 1/ε, presenting exponential improvements in 1/ε over current algorithms. We complement our results by showing lower bounds of (1/ε)^Ω(d) for any 1-pass algorithm solving the (1 + ε)-approximation MEB and linear SVM problems, further motivating our multi-pass approach.
Cite as

N. Efe Çekirge, William Gay, and David P. Woodruff. Multipass Linear Sketches for Geometric LP-Type Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 8:1-8:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cekirge_et_al:LIPIcs.APPROX/RANDOM.2025.8,
  author =	{\c{C}ekirge, N. Efe and Gay, William and Woodruff, David P.},
  title =	{{Multipass Linear Sketches for Geometric LP-Type Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{8:1--8:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.8},
  URN =		{urn:nbn:de:0030-drops-243741},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.8},
  annote =	{Keywords: Streaming, sketching, LP-type problems}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.8
An Axiomatic Study of Leveraging Blockers to Self-Assemble Arbitrary Shapes via Temperature Programming

Authors: Matthew J. Patitz and Trent A. Rogers

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
In this paper we present a theoretical design for tile-based self-assembling systems where individual tile sets that are universal for various tasks (e.g. building shapes or encoding arbitrary data for algorithmic systems) can be provided their input solely using sequences of variations in temperatures. Although there is prior theoretical work in so-called "temperature programming," the results presented here are based upon recent experimental work with "blocked tiles" that provides plausible evidence for their practical implementation. We develop and present an abstract mathematical model, the BlockTAM, for such systems that is based upon the experimental work, and provide constructions within it for universal number encoding systems and a universal shape building construction. These results mirror previous results in temperature programming, covering the two ends of the spectrum that seek to balance the scale factors of assemblies with the number of temperature phases required, while leveraging the features of the BlockTAM that we hope provide a pathway for future experimental implementations.
Cite as

Matthew J. Patitz and Trent A. Rogers. An Axiomatic Study of Leveraging Blockers to Self-Assemble Arbitrary Shapes via Temperature Programming. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{patitz_et_al:LIPIcs.DNA.31.8,
  author =	{Patitz, Matthew J. and Rogers, Trent A.},
  title =	{{An Axiomatic Study of Leveraging Blockers to Self-Assemble Arbitrary Shapes via Temperature Programming}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{8:1--8:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.8},
  URN =		{urn:nbn:de:0030-drops-238574},
  doi =		{10.4230/LIPIcs.DNA.31.8},
  annote =	{Keywords: DNA tiles, self-assembly, temperature programming}
}
Document
DOI: 10.4230/LIPIcs.DNA.31.9
Synchronous Versus Asynchronous Tile-Based Self-Assembly

Authors: Florent Becker, Phillip Drake, Matthew J. Patitz, and Trent A. Rogers

Published in: LIPIcs, Volume 347, 31st International Conference on DNA Computing and Molecular Programming (DNA 31) (2025)

Abstract
In this paper we study the relationship between mathematical models of tile-based self-assembly which differ in terms of the synchronicity of tile additions. In the standard abstract Tile Assembly Model (aTAM), each step of assembly consists of a single tile being added to an assembly. At any given time, each location on the perimeter of an assembly to which a tile can legally bind is called a frontier location, and for each step of assembly one frontier location is randomly selected and a tile is added. In the Synchronous Tile Assembly Model (syncTAM), at each step of assembly every frontier location simultaneously receives a tile. Our results show that while directed, non-cooperative syncTAM systems are capable of universal computation (while directed, non-cooperative aTAM systems are known not to be), and they are capable of building shapes that can't be built within the aTAM, the non-cooperative aTAM is also capable of building shapes that can't be built within the syncTAM even cooperatively. We show a variety of results that demonstrate the similarities and differences between these two models.
Cite as

Florent Becker, Phillip Drake, Matthew J. Patitz, and Trent A. Rogers. Synchronous Versus Asynchronous Tile-Based Self-Assembly. In 31st International Conference on DNA Computing and Molecular Programming (DNA 31). Leibniz International Proceedings in Informatics (LIPIcs), Volume 347, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.DNA.31.9,
  author =	{Becker, Florent and Drake, Phillip and Patitz, Matthew J. and Rogers, Trent A.},
  title =	{{Synchronous Versus Asynchronous Tile-Based Self-Assembly}},
  booktitle =	{31st International Conference on DNA Computing and Molecular Programming (DNA 31)},
  pages =	{9:1--9:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-399-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{347},
  editor =	{Schaeffer, Josie and Zhang, Fei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DNA.31.9},
  URN =		{urn:nbn:de:0030-drops-238580},
  doi =		{10.4230/LIPIcs.DNA.31.9},
  annote =	{Keywords: self-assembly, noncooperative self-assembly, models of computation, tile assembly systems}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.74
Drainability and Fillability of Polyominoes in Diverse Models of Global Control

Authors: Sándor P. Fekete, Peter Kramer, Jan-Marc Reinhardt, Christian Rieck, and Christian Scheffer

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
Tilt models offer intuitive and clean definitions of complex systems in which particles are influenced by global control commands. Despite a wide range of applications, there has been almost no theoretical investigation into the associated issues of filling and draining geometric environments. This is partly because a globally controlled system (i.e., passive matter) exhibits highly complex behavior that cannot be locally restricted. Thus, there is a strong need for theoretical studies that investigate these models both (1) in terms of relative power to each other, and (2) from a complexity theory perspective. In this work, we provide (1) general tools for comparing and contrasting different models of global control, and (2) both complexity and algorithmic results on filling and draining.
Cite as

Sándor P. Fekete, Peter Kramer, Jan-Marc Reinhardt, Christian Rieck, and Christian Scheffer. Drainability and Fillability of Polyominoes in Diverse Models of Global Control. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 74:1-74:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.ICALP.2025.74,
  author =	{Fekete, S\'{a}ndor P. and Kramer, Peter and Reinhardt, Jan-Marc and Rieck, Christian and Scheffer, Christian},
  title =	{{Drainability and Fillability of Polyominoes in Diverse Models of Global Control}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{74:1--74:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.74},
  URN =		{urn:nbn:de:0030-drops-234518},
  doi =		{10.4230/LIPIcs.ICALP.2025.74},
  annote =	{Keywords: Global control, full Tilt, single Tilt, Fillability, Drainability, Polyominoes, Complexity}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2021.62
Can You Walk This? Eulerian Tours and IDEA Instructions (Media Exposition)

Authors: Aaron T. Becker, Sándor P. Fekete, Matthias Konitzny, Sebastian Morr, and Arne Schmidt

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We illustrate and animate the classic problem of deciding whether a given graph has an Eulerian path. Starting with a collection of instances of increasing difficulty, we present a set of pictorial instructions, and show how they can be used to solve all instances. These IDEA instructions ("A series of nonverbal algorithm assembly instructions") have proven to be both entertaining for experts and enlightening for novices. We (w)rap up with a song and dance to Euler’s original instance.
Cite as

Aaron T. Becker, Sándor P. Fekete, Matthias Konitzny, Sebastian Morr, and Arne Schmidt. Can You Walk This? Eulerian Tours and IDEA Instructions (Media Exposition). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 62:1-62:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SoCG.2021.62,
  author =	{Becker, Aaron T. and Fekete, S\'{a}ndor P. and Konitzny, Matthias and Morr, Sebastian and Schmidt, Arne},
  title =	{{Can You Walk This? Eulerian Tours and IDEA Instructions}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{62:1--62:4},
  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.62},
  URN =		{urn:nbn:de:0030-drops-138616},
  doi =		{10.4230/LIPIcs.SoCG.2021.62},
  annote =	{Keywords: Eulerian tours, algorithms, education, IDEA instructions}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2020.72
Coordinated Particle Relocation with Global Signals and Local Friction (Media Exposition)

Authors: Victor M. Baez, Aaron T. Becker, Sándor P. Fekete, and Arne Schmidt

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
In this video, we present theoretical and practical methods for achieving arbitrary reconfiguration of a set of objects, based on the use of external forces, such as a magnetic field or gravity: Upon actuation, each object is pushed in the same direction. This concept can be used for a wide range of applications in which particles do not have their own energy supply or in which they are subject to the same global control commands. A crucial challenge for achieving any desired target configuration is breaking global symmetry in a controlled fashion. Previous work (some of which was presented during SoCG 2015) made use of specifically placed barriers; however, introducing precisely located obstacles into the workspace is impractical for many scenarios. In this paper, we present a different, less intrusive method: making use of the interplay between static friction with a boundary and the external force to achieve arbitrary reconfiguration. Our key contributions are theoretical characterizations of the critical coefficient of friction that is sufficient for rearranging two particles in triangles, convex polygons, and regular polygons; a method for reconfiguring multiple particles in rectangular workspaces, and deriving practical algorithms for these rearrangements. Hardware experiments show the efficacy of these procedures, demonstrating the usefulness of this novel approach.
Cite as

Victor M. Baez, Aaron T. Becker, Sándor P. Fekete, and Arne Schmidt. Coordinated Particle Relocation with Global Signals and Local Friction (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 72:1-72:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{baez_et_al:LIPIcs.SoCG.2020.72,
  author =	{Baez, Victor M. and Becker, Aaron T. and Fekete, S\'{a}ndor P. and Schmidt, Arne},
  title =	{{Coordinated Particle Relocation with Global Signals and Local Friction}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{72:1--72:5},
  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.72},
  URN =		{urn:nbn:de:0030-drops-122305},
  doi =		{10.4230/LIPIcs.SoCG.2020.72},
  annote =	{Keywords: Global control, reconfiguration, geometric algorithms, friction}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2020.73
Space Ants: Constructing and Reconfiguring Large-Scale Structures with Finite Automata (Media Exposition)

Authors: Amira Abdel-Rahman, Aaron T. Becker, Daniel E. Biediger, Kenneth C. Cheung, Sándor P. Fekete, Neil A. Gershenfeld, Sabrina Hugo, Benjamin Jenett, Phillip Keldenich, Eike Niehs, Christian Rieck, Arne Schmidt, Christian Scheffer, and Michael Yannuzzi

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
In this video, we consider recognition and reconfiguration of lattice-based cellular structures by very simple robots with only basic functionality. The underlying motivation is the construction and modification of space facilities of enormous dimensions, where the combination of new materials with extremely simple robots promises structures of previously unthinkable size and flexibility. We present algorithmic methods that are able to detect and reconfigure arbitrary polyominoes, based on finite-state robots, while also preserving connectivity of a structure during reconfiguration. Specific results include methods for determining a bounding box, scaling a given arrangement, and adapting more general algorithms for transforming polyominoes.
Cite as

Amira Abdel-Rahman, Aaron T. Becker, Daniel E. Biediger, Kenneth C. Cheung, Sándor P. Fekete, Neil A. Gershenfeld, Sabrina Hugo, Benjamin Jenett, Phillip Keldenich, Eike Niehs, Christian Rieck, Arne Schmidt, Christian Scheffer, and Michael Yannuzzi. Space Ants: Constructing and Reconfiguring Large-Scale Structures with Finite Automata (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 73:1-73:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{abdelrahman_et_al:LIPIcs.SoCG.2020.73,
  author =	{Abdel-Rahman, Amira and Becker, Aaron T. and Biediger, Daniel E. and Cheung, Kenneth C. and Fekete, S\'{a}ndor P. and Gershenfeld, Neil A. and Hugo, Sabrina and Jenett, Benjamin and Keldenich, Phillip and Niehs, Eike and Rieck, Christian and Schmidt, Arne and Scheffer, Christian and Yannuzzi, Michael},
  title =	{{Space Ants: Constructing and Reconfiguring Large-Scale Structures with Finite Automata}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{73:1--73:6},
  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.73},
  URN =		{urn:nbn:de:0030-drops-122310},
  doi =		{10.4230/LIPIcs.SoCG.2020.73},
  annote =	{Keywords: Finite automata, reconfiguration, construction, scaling}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2020.74
How to Make a CG Video (Media Exposition)

Authors: Aaron T. Becker and Sándor P. Fekete

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
In this video we describe why producing a Computational Geometry video is a good idea, what it takes to make one, and how to actually do it. This includes a guide for the overall process, a number of examples, and a variety of tips and tricks.
Cite as

Aaron T. Becker and Sándor P. Fekete. How to Make a CG Video (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 74:1-74:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SoCG.2020.74,
  author =	{Becker, Aaron T. and Fekete, S\'{a}ndor P.},
  title =	{{How to Make a CG Video}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{74:1--74:6},
  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.74},
  URN =		{urn:nbn:de:0030-drops-122328},
  doi =		{10.4230/LIPIcs.SoCG.2020.74},
  annote =	{Keywords: Videos, animation, education, SoCG Multimedia}
}
Document
Multimedia Exposition
DOI: 10.4230/LIPIcs.SoCG.2019.63
Packing Geometric Objects with Optimal Worst-Case Density (Multimedia Exposition)

Authors: Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Sebastian Morr, and Christian Scheffer

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
We motivate and visualize problems and methods for packing a set of objects into a given container, in particular a set of {different-size} circles or squares into a square or circular container. Questions of this type have attracted a considerable amount of attention and are known to be notoriously hard. We focus on a particularly simple criterion for deciding whether a set can be packed: comparing the total area A of all objects to the area C of the container. The critical packing density delta^* is the largest value A/C for which any set of area A can be packed into a container of area C. We describe algorithms that establish the critical density of squares in a square (delta^*=0.5), of circles in a square (delta^*=0.5390 ...), regular octagons in a square (delta^*=0.5685 ...), and circles in a circle (delta^*=0.5).
Cite as

Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Sebastian Morr, and Christian Scheffer. Packing Geometric Objects with Optimal Worst-Case Density (Multimedia Exposition). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 63:1-63:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SoCG.2019.63,
  author =	{Becker, Aaron T. and Fekete, S\'{a}ndor P. and Keldenich, Phillip and Morr, Sebastian and Scheffer, Christian},
  title =	{{Packing Geometric Objects with Optimal Worst-Case Density}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{63:1--63:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.63},
  URN =		{urn:nbn:de:0030-drops-104678},
  doi =		{10.4230/LIPIcs.SoCG.2019.63},
  annote =	{Keywords: Packing, complexity, bounds, packing density}
}
Document
Multimedia Exposition
DOI: 10.4230/LIPIcs.SoCG.2018.74
Coordinated Motion Planning: The Video (Multimedia Exposition)

Authors: Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Matthias Konitzny, Lillian Lin, and Christian Scheffer

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
We motivate, visualize and demonstrate recent work for minimizing the total execution time of a coordinated, parallel motion plan for a swarm of N robots in the absence of obstacles. Under relatively mild assumptions on the separability of robots, the algorithm achieves constant stretch: If all robots want to move at most d units from their respective starting positions, then the total duration of the overall schedule (and hence the distance traveled by each robot) is O(d) steps; this implies constant-factor approximation for the optimization problem. Also mentioned is an NP-hardness result for finding an optimal schedule, even in the case in which robot positions are restricted to a regular grid. On the other hand, we show that for densely packed disks that cannot be well separated, a stretch factor Omega(N^{1/4}) is required in the worst case; we establish an achievable stretch factor of O(N^{1/2}) even in this case. We also sketch geometric difficulties of computing optimal trajectories, even for just two unit disks.
Cite as

Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Matthias Konitzny, Lillian Lin, and Christian Scheffer. Coordinated Motion Planning: The Video (Multimedia Exposition). In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 74:1-74:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SoCG.2018.74,
  author =	{Becker, Aaron T. and Fekete, S\'{a}ndor P. and Keldenich, Phillip and Konitzny, Matthias and Lin, Lillian and Scheffer, Christian},
  title =	{{Coordinated Motion Planning: The Video}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{74:1--74:6},
  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.74},
  URN =		{urn:nbn:de:0030-drops-87872},
  doi =		{10.4230/LIPIcs.SoCG.2018.74},
  annote =	{Keywords: Motion planning, robot swarms, complexity, stretch, approximation}
}
  • Refine by Type
  • 18 Document/PDF
  • 9 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 8 2025
  • 1 2021
  • 3 2020
  • 1 2019
  • Show More...

  • Refine by Author
  • 11 Fekete, Sándor P.
  • 9 Becker, Aaron T.
  • 5 Scheffer, Christian
  • 4 Keldenich, Phillip
  • 4 Rieck, Christian
  • Show More...

  • Refine by Series/Journal
  • 16 LIPIcs
  • 2 OASIcs

  • Refine by Classification
  • 6 Theory of computation → Computational geometry
  • 3 Theory of computation → Models of computation
  • 2 Applied computing → Education
  • 1 Computer systems organization → Embedded and cyber-physical systems
  • 1 Computing methodologies → Interactive simulation
  • Show More...

  • Refine by Keyword
  • 4 complexity
  • 2 Global control
  • 2 approximation
  • 2 education
  • 2 global control
  • 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