03/20/2026
By Frederick Stock

The Miner School of Computer and Information Sciences, Department of Computer Science, invites you to attend a doctoral dissertation defense by Frederick Stock on “Reconfiguration Algorithms in Lattice Graphs: Modular Robots and Redistricting."

Candidate Name: Frederick Stock
Degree: Doctoral
Defense Date: Friday, April, 3, 2026
Time : 1 - 2 p.m.
Location: Dandeneau 309, North Campus
Thesis/Dissertation Title: Reconfiguration Algorithms in Lattice Graphs: Modular Robots and Redistricting

Committee:

  • Advisor: Hugo A. Akitaya, Miner School of Computer and Information Sciences, UML
  • Erik D. Demaine, Ph.D., Computer Science and Artificial Intelligence Laboratory, MIT
  • Anitha Gollamundi, Ph.D., Miner School of Computer and Information Sciences, UML
  • Amanda Redlich, Ph.D., Department of Mathematics & Statistics, UML

Brief 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. 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.

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. Theoretical results on the power of these moves are of interest as they guarantee desirable properties of the sampling method, 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 recombinations. We simplify their proofs, as well as strengthening their algorithm for the triangular grid, and further extending it to districts in a square grid.