55 citations · 134 across the 13 of their papers we have counts for
16 papers
Irreducibility of Recombination Markov Chains in the Triangular Lattice
Sarah Cannon
In the United States, regions are frequently divided into districts for the purpose of electing representatives. How the districts are drawn can affect who's elected, and drawing d…
Spanning Trees and Redistricting: New Methods for Sampling and Validation
Sarah Cannon, Moon Duchin, Dana Randall +1
Deciding whether a political districting plan was distorted by a hidden agenda, or whether it dilutes the voting power of some group, requires a neutral baseline for comparison. Re…
Fast and perfect sampling of subgraphs and polymer systems
Antonio Blanca, Sarah Cannon, Will Perkins
We give an efficient perfect sampling algorithm for weighted, connected induced subgraphs (or graphlets) of rooted, bounded degree graphs. Our algorithm utilizes a vertex-percolati…
Voting Rights, Markov Chains, and Optimization by Short Bursts
Sarah Cannon, Ari Goldbloom-Helzner, Varun Gupta +2
Finding outlying elements in probability distributions can be a hard problem. Taking a real example from Voting Rights Act enforcement, we consider the problem of maximizing the nu…
Programming Active Cohesive Granular Matter with Mechanically Induced Phase Changes
Shengkai Li, Bahnisikha Dutta, Sarah Cannon +6
Active matter physics and swarm robotics have provided powerful tools for the study and control of ensembles driven by internal sources. At the macroscale, controlling swarms typic…
Counting independent sets in unbalanced bipartite graphs
Sarah Cannon, Will Perkins
We give an FPTAS for approximating the partition function of the hard-core model for bipartite graphs when there is sufficient imbalance in the degrees or fugacities between the si…
A Local Stochastic Algorithm for Separation in Heterogeneous Self-Organizing Particle Systems
Sarah Cannon, Joshua J. Daymude, Cem Gokmen +2
We present and rigorously analyze the behavior of a distributed, stochastic algorithm for separation and integration in self-organizing particle systems, an abstraction of programm…
Phototactic Supersmarticles
Sarah Cannon, Joshua J. Daymude, William Savoie +5
Smarticles, or smart active particles, are small robots equipped with only basic movement and sensing abilities that are incapable of rotating or displacing individually. We study…
A Stochastic Approach to Shortcut Bridging in Programmable Matter
Marta Andrés Arroyo, Sarah Cannon, Joshua J. Daymude +2
In a self-organizing particle system, an abstraction of programmable matter, simple computational elements called particles with limited memory and communication self-organize to s…
Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings
Sarah Cannon, David Levin, Alexandre Stauffer
We give the first polynomial upper bound on the mixing time of the edge-flip Markov chain for unbiased dyadic tilings, resolving an open problem originally posed by Janson, Randall…
A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems
Sarah Cannon, Joshua J. Daymude, Dana Randall +1
In systems of programmable matter, we are given a collection of simple computation elements (or particles) with limited (constant-size) memory. We are interested in when they can s…
Combinatorics and complexity of guarding polygons with edge and point 2-transmitters
Sarah Cannon, Thomas G. Fai, Justin Iwerks +2
We consider a generalization of the classical Art Gallery Problem, where instead of a light source, the guards, called -transmitters, model a wireless device with a signal that…
Diffuse Reflection Diameter in Simple Polygons
Gill Barequet, Sarah M. Cannon, Eli Fox-Epstein +4
We prove a conjecture of Aanjaneya, Bishnu, and Pal that the minimum number of diffuse reflections sufficient to illuminate the interior of any simple polygon with walls from a…
Hidden Mobile Guards in Simple Polygons
Sarah Cannon, Diane L. Souvaine, Andrew Winslow
We consider guarding classes of simple polygons using mobile guards (polygon edges and diagonals) under the constraint that no two guards may see each other. In contrast to most ot…
Conflict-free graph orientations with parity constraints
Sarah Cannon, Mashhood Ishaque, Csaba Tóth
It is known that every multigraph with an even number of edges has an even orientation (i.e., all indegrees are even). We study parity constrained graph orientations under addition…
Two Hands Are Better Than One (up to constant factors)
Sarah Cannon, Erik D. Demaine, Martin L. Demaine +5
We study the difference between the standard seeded model of tile self-assembly, and the "seedless" two-handed model of tile self-assembly. Most of our results suggest that the two…