My research interests include theoretical computer science; randomized algorithms; Markov chains; approximate sampling and counting; discrete geometry; discrete mathematics; emergent behavior; programmable matter; statistical physics; the cluster expansion; and the mathematics of redistricting. More details on my previous work using Markov chains to develop distributed algorithms for programmable matter, including simulations, can be found on our research group's website.
- "A reversible recombination chain for graph partitions." Sarah Cannon, Moon Duchin, Dana Randall, and Parker Rule. In preparation.
- "Fast and perfect sampling of subgraphs and polymer systems." Antonio Blanca, Sarah Cannon, and Will Perkins. Sumbitted.
- "Voting Rights, Markov Chains, and Optimization by Short Bursts." Sarah Cannon, Ari Goldbloom-Helzner, Varun Gupta, JN Matthews, and Bhushan Suwal. Submitted.
- "Programming active cohesive granular matter with mechanically induced phase changes." Shengkai Li, Bahnisikha Dutta, Sarah Cannon, Joshua J. Daymude, Ram Avinery, Enes Aydin, Andréa W. Richa, Daniel I. Goldman, Dana Randall. Science Advances, Vol. 7, No. 17, eabe8494, 2021.
- "Counting independent sets in unbalanced bipartite graphs." Sarah Cannon and Will Perkins. 2020 ACM-SIAM Symposium on Discrete Algorithms (SODA), 2020.
- "A local stochastic algorithm for separation in heterogeneous self-organizing particle systems." Sarah Cannon, Joshua J. Daymude, Cem Gokmen, Dana Randall, and Andréa W. Richa. 23rd International Workshop on Randomization and Computation (RANDOM), 2019. Preliminary results appeared as a Brief Announcement at the ACM Symposium on Principles of Distributed Computing (PODC), 2018.
- "Polynomial mixing of the edge-flip Markov chain for unbiased dyadic tilings." Sarah Cannon, David Levin, and Alexandre Stauffer. Combinatorics, Probability, and Computing 28(3), pp. 365-387, 2019. Previously in: 21st International Workshop on Randomization and Computation (RANDOM), 2017.
- "Phototactic Supersmarticles." William Savoie, Sarah Cannon, Joshua J. Daymude, Ross Warkentin, Shengkai Li, Dana Randall, Andréa W. Richa, and Daniel I. Goldman. Artificial Life and Robotics 23(4), pp. 459-468, 2018. Previously in: 2nd International Symposium on Swarm Behavior and Bio-Inspired Robotics (SWARM), 2017.
- "A Stochastic Approach to Shortcut Bridging in Programmable Matter." Marta Andrés Arroyo, Sarah Cannon, Joshua J. Daymude, Dana Randall, and Andréa W. Richa. Natural Computing 17(4), pp. 723-741, 2018. Previously in: 23rd International Conference on DNA Computing and Molecular Programming (DNA), 2017.
- "Phase Transitions in Random Dyadic Tilings and Rectangular Dissections." Sarah Cannon, Sarah Miracle and Dana Randall. SIAM Journal on Discrete Mathematics, 32(3), pp. 1966-1992, 2018. Previously in: 26th Symposium on Discrete Algorithms (SODA), 2015.
- "Combinatorics and complexity of guarding polygons with edge and point 2-transmitters." Sarah Cannon, Thomas G. Fai, Justin Iwerks, Undine Leopold and Christiane Schmidt. Computational Geometry, vol. 68, pp. 89-100, 2018. Previously appeared as "Combinatorics of edge 2-transmitter art gallery problems," European Conference on Computational Geometry (EuroCG), 2015, and as "NP-hardness of the minimum point and edge 2-transmitter cover problem," 24th Fall Workshop on Computational Geometry (FWCG), 2014.
- "A Markov Chain Algorithm for Compression in Self-Organizing Particle Systems." Sarah Cannon, Joshua J. Daymude, Dana Randall, and Andréa Richa. ACM Symposium on Principles of Distributed Computing (PODC), 2016.
- "Sampling on lattices with free boundary conditions using randomized extensions." Sarah Cannon and Dana Randall. 27th Symposium on Discrete Algorithms (SODA), 2016.
- "Diffuse reflection diameter in simple polygons." Gill Barequet, Sarah Cannon, Eli Fox-Epstein, Benjamin Hescott, Diane L. Souvaine, Csaba D. Töth and Andrew Winslow. Discrete Applied Mathematics, vol. 210, pp. 123-132, 2016. Previously appeared in Latin-American Algorithms, Graphs, and Optimization Symposium (LAGOS), 2013.
- "Embeddedness for singly periodic Scherk surfaces with higher dihedral symmetry." Valmir Bucaj, Sarah Cannon, Michael Dorff, Jamal Lawson and Ryan Viertel. Involve: a journal of mathematics, 6(4): 383-392, 2013.
- "Two Hands are Better than one (up to constant factors): self-assembly in the 2HAM vs. aTAM." Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert Schweller, Scott M. Summers and Andrew Winslow. Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS), 2013.
- "Hidden mobile guards in simple polygons." Sarah Cannon, Diane L. Souvaine and Andrew Winslow. In Abstracts of the 24th Canadian Conference on Computational Geometry (CCCG), 2012. Preliminary results presented at the Fall Workshop on Computational Geometry (FWCG), 2011.
- "Conflict-free graph orientations with parity constraints." Sarah Cannon, Mashhood Ishaque and Csaba D. Tóth. Proceedings of the Sixth International Conference on Fun with Algorithms (FUN), 2012. Preliminary results presented at the Fall Workshop on Computational Geometry (FWCG), 2010.