We prove PSPACE-completeness of the well-studied pushing-block puzzle Push-1F, a
theoretical abstraction of many video games (introduced in 1999). The proof also extends to …

The popularity of molecular computation has given rise to several models of abstraction, one
of the more recent ones being Chemical Reaction Networks (CRNs). These are equivalent …

We analyze the computational complexity of basic reconfiguration problems for the recently
introduced surface Chemical Reaction Networks (sCRNs), where ordered pairs of adjacent …

This thesis develops a framework for proving computational complexity results about motion
planning problems. The model captures reactive environments with local interaction. We …

We extend the motion-planning-through-gadgets framework to several new scenarios
involving various numbers of robots/agents, and analyze the complexity of the resulting …

We prove RE-completeness (and thus undecidability) of several 2D games in the Super
Mario Bros. platform video game series: the New Super Mario Bros. series (original, Wii, U …

Since the turn of the 21st century, seeing the decline of Moore's Law on the horizon, the
pursuit of continued software performance gains has led to the prominence of computer …

As it becomes increasingly harder to make transistors smaller, replacements for traditional
silicon computers become sought after. To study the computing power of these potential …

Recently developed motion planning techniques lend powerful tools to formulate insights
across numerous research fields. This work investigates the application of motion planning …

The 33rd International Workshop on Combinatorial Algorithms (IWOCA 2022) was planned
as a hybrid event, with the on-site activities taking place at the University of Trier, Germany …