09/24/2025
By Frederick Stock

Canidate Name: Frederick Stock
Degree: Doctoral
Defense Date: Wednesday, Oct. 1, 2025
Time: 1 - 2 p.m. EST
Location: Hybrid Dan 309 or via Zoom.

Committee Members:

  • Hugo Akitaya, Assistant Professor, Miner School of Computer & Information Sciences
  • Anitha Gollamundi, Assistant Professor, Miner School of Computer & Information Sciences
  • Amanda Redlich, Assistant Professor, Kennedy College of Sciences
  • Erik Demaine, Professor, MIT Computer Science and Artificial Intelligence Laboratory

Abstract:
Reconfiguration is a fundamental problem in many contexts. At its core a reconfiguration problem ask if one object can be transformed into another following some set of constraints. This dissertation will study two particular reconfiguration problems that are of interest to the scientific community. Reconfiguration of modular robots, and reconfiguration of district maps for redistricting.

Modular robots (or Programmable Matter) are a growing area of interest. The goal of these systems is to use many small, simple robots working together to form a larger robotic system. This would therefore create a adaptable and robust system. As each small robot is easily replaceable, and can move around its neighbors to reconfigure the larger system to handle tasks ad hoc. Introduced only a few decades ago, many models of modular robot have been studied, theoretically and physically. One of the oldest models is sliding squares or cubes. Where each robot is a d-dimensional cube, and can slide along d-1 dimensional faces of adjacent robots. This model is popular in the theoretical community for its simplicity, and strong algorithmic results. We investigated and resolved the long standing open problem of reconfiguration of 3-dimensional (and higher) sliding cubes. As well as parallel reconfiguration of sliding (two dimensional) squares.

Reconfiguration algorithms for redistricting are also considered. Redistricting is a topic great contemporary interest, in particular with regard to gerrymandering. It is a difficult task to determine if a district map is gerrymandered. One method practitioners often use to evaluate the quality of district plans is random sampling. This approach involves comparing a proposed plan to an ensemble of randomly generated alternatives to determine whether it is an outlier, potentially suggesting an unfair plan. This random sampling often uses a Markovian model, based on a process called a recombination move. Which is a reconfiguration of districts within the map. Theoretical results on the power of these moves are of interest as they guarantee desirable properties of the overarching model, such as irreducibility of the Markov chain. A recent result by Cannon shows that this move on districts in a triangular lattice, is universal, i.e. any district map can be reconfigured into another with only recombination. We simplify their proofs, as well as strengthening their algorithm for the triangular grid, and further extending it to districts in a square grid.