b'Jayson Lynch'

research

∙ 08/29/2023

When Can You Tile an Integer Rectangle with Integer Squares?

This paper characterizes when an m × n rectangle, where m and n are inte...

0 MIT CompGeom Group, et al. ∙

research

∙ 06/01/2023

Complexity of Motion Planning of Arbitrarily Many Robots: Gadgets, Petri Nets, and Counter Machines

We extend the motion-planning-through-gadgets framework to several new s...

0 Joshua Ani, et al. ∙

research

∙ 03/27/2023

Complexity of Reconfiguration in Surface Chemical Reaction Networks

We analyze the computational complexity of basic reconfiguration problem...

0 Robert M. Alaniz, et al. ∙

research

∙ 02/02/2023

Complexity of Solo Chess with Unlimited Moves

We analyze Solo Chess puzzles, where the input is an n × n board contain...

0 Josh Brunner, et al. ∙

research

∙ 02/02/2023

This Game Is Not Going To Analyze Itself

We analyze the puzzle video game This Game Is Not Going To Load Itself, ...

0 Aviv Adler, et al. ∙

research

∙ 12/23/2022

Computational Complexity of Flattening Fixed-Angle Orthogonal Chains

Planar/flat configurations of fixed-angle chains and trees are well stud...

0 Erik D. Demaine, et al. ∙

research

∙ 11/26/2022

Lower Bounds on Retroactive Data Structures

We prove essentially optimal fine-grained lower bounds on the gap betwee...

0 Lily Chung, et al. ∙

research

∙ 09/21/2022

Characterizing the Decidability of Finite State Automata Team Games with Communication

In this paper we define a new model of limited communication for multipl...

0 Michael Coulombe, et al. ∙

research

∙ 07/14/2022

PSPACE-Completeness of Reversible Deterministic Systems

We prove PSPACE-completeness of several reversible, fully deterministic ...

0 Erik D. Demaine, et al. ∙

research

∙ 06/08/2022

Reconfiguration of Non-crossing Spanning Trees

For a set P of n points in the plane in general position, a non-crossing...

0 Oswin Aichholzer, et al. ∙

research

∙ 04/01/2022

Traversability, Reconfiguration, and Reachability in the Gadget Framework

Consider an agent traversing a graph of "gadgets", each with local state...

0 Joshua Ani, et al. ∙

research

∙ 03/31/2022

The Legend of Zelda: The Complexity of Mechanics

We analyze some of the many game mechanics available to Link in the clas...

0 Jeffrey Bosboom, et al. ∙

research

∙ 10/27/2021

An Efficient Reversible Algorithm for Linear Regression

This paper presents an efficient reversible algorithm for linear regress...

0 Erik D. Demaine, et al. ∙

research

∙ 10/26/2021

The Computational Complexity of Finding Arithmetic Expressions With and Without Parentheses

We show NP-completeness for various problems about the existence of arit...

0 Jayson Lynch, et al. ∙

research

∙ 09/23/2021

Multidimensional Scaling: Approximation and Complexity

Metric Multidimensional scaling (MDS) is a classical method for generati...

0 Erik Demaine, et al. ∙

research

∙ 08/26/2021

Optimal-area visibility representations of outer-1-plane graphs

This paper studies optimal-area visibility representations of n-vertex o...

0 Therese Biedl, et al. ∙

research

∙ 06/29/2021

Yin-Yang Puzzles are NP-complete

We prove NP-completeness of Yin-Yang / Shiromaru-Kuromaru pencil-and-pap...

0 Erik D. Demaine, et al. ∙

research

∙ 05/22/2021

Continuous Flattening of All Polyhedral Manifolds using Countably Infinite Creases

We prove that any finite polyhedral manifold in 3D can be continuously f...

0 Zachary Abel, et al. ∙

research

∙ 05/18/2021

Snipperclips: Cutting Tools into Desired Polygons using Themselves

We study Snipperclips, a computer puzzle game whose objective is to crea...

0 Zachary Abel, et al. ∙

research

∙ 05/14/2021

Generalized LR-drawings of trees

The LR-drawing-method is a method of drawing an ordered rooted binary tr...

0 Therese Biedl, et al. ∙

research

∙ 03/11/2021

Hardness of Token Swapping on Trees

Given a graph where every vertex has exactly one labeled token, how can ...

0 Oswin Aichholzer, et al. ∙

research

∙ 12/14/2020

Characterizing Universal Reconfigurability of Modular Pivoting Robots

We give both efficient algorithms and hardness results for reconfiguring...

0 Hugo A. Akitaya, et al. ∙

research

∙ 11/23/2020

Arithmetic Expression Construction

When can n given numbers be combined using arithmetic operators from a g...

0 Leo Alcock, et al. ∙

research

∙ 10/17/2020

Mad Science is Provably Hard: Puzzles in Hearthstone's Boomsday Lab are NP-hard

We consider the computational complexity of winning this turn (mate-in-1...

0 Michael Hoffmann, et al. ∙

research

∙ 09/29/2020

Tetris is NP-hard even with O(1) rows or columns

We prove that the classic falling-block video game Tetris (both survival...

0 Sualeh Asif, et al. ∙

research

∙ 07/17/2020

Escaping a Polygon

Suppose an "escaping" player moves continuously at maximum speed 1 in th...

0 Zachary Abel, et al. ∙

research

∙ 06/08/2020

PSPACE-completeness of Pulling Blocks to Reach a Goal

We prove PSPACE-completeness of all but one problem in a large space of ...

0 Joshua Ani, et al. ∙

research

∙ 06/01/2020

Walking through Doors is Hard, even without Staircases: Proving PSPACE-hardness via Planar Assemblies of Door Gadgets

A door gadget has two states and three tunnels that can be traversed by ...

0 Joshua Ani, et al. ∙

research

∙ 06/01/2020

Negative Instance for the Edge Patrolling Beacon Problem

Can an infinite-strength magnetic beacon always “catch” an iron ball, wh...

0 Zachary Abel, et al. ∙

research

∙ 05/07/2020

Trains, Games, and Complexity: 0/1/2-Player Motion Planning through Input/Output Gadgets

We analyze the computational complexity of motion planning through local...

0 Joshua Ani, et al. ∙

research

∙ 03/18/2020

Tatamibari is NP-complete

In the Nikoli pencil-and-paper game Tatamibari, a puzzle consists of an ...

0 Aviv Adler, et al. ∙

research

∙ 02/12/2020

Recursed is not Recursive: A Jarring Result

Recursed is a 2D puzzle platform video game featuring treasure chests th...

0 Erik Demaine, et al. ∙

research

∙ 09/30/2019

Hamiltonicity in Semi-Regular Tessellation Dual Graphs

This paper shows NP-completeness for finding Hamiltonian cycles in induc...

0 Divya Gopinath, et al. ∙

research

∙ 04/19/2019

Data Races and the Discrete Resource-time Tradeoff Problem with Resource Reuse over Paths

A determinacy race occurs if two or more logically parallel instructions...

0 Rathish Das, et al. ∙

research

∙ 12/10/2018

A General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard

We build a general theory for characterizing the computational complexit...

0 Erik D. Demaine, et al. ∙

research

∙ 08/22/2018

Cookie Clicker

Cookie Clicker is a popular online incremental game where the goal of th...

0 Erik D. Demaine, et al. ∙

research

∙ 06/14/2018

Losing at Checkers is Hard

We prove computational intractability of variants of checkers: (1) decid...

0 Jeffrey Bosboom, et al. ∙

research

∙ 06/09/2018

Computational Complexity of Motion Planning of a Robot through Simple Gadgets

We initiate a general theory for analyzing the complexity of motion plan...

0 Erik D. Demaine, et al. ∙

research

∙ 05/08/2018

The Computational Complexity of Finding Hamiltonian Cycles in Grid Graphs of Semiregular Tessellations

Finding Hamitonian Cycles in square grid graphs is a well studied and im...

0 Kaiying Hou, et al. ∙

research

∙ 04/26/2018

Who witnesses The Witness? Finding witnesses in The Witness is hard and sometimes impossible

We analyze the computational complexity of the many types of pencil-and-...

0 Zachary Abel, et al. ∙

research

∙ 11/21/2017

Fine-Grained I/O Complexity via Reductions: New lower bounds, faster algorithms, and a time hierarchy

This paper initiates the study of I/O algorithms (minimizing cache misse...

0 Erik D. Demaine, et al. ∙

research

∙ 09/05/2017

Push-Pull Block Puzzles are Hard

This paper proves that push-pull block puzzles in 3D are PSPACE-complete...

0 Erik D. Demaine, et al. ∙

Jayson Lynch

Featured Co-authors