Sarah Cannon

Algorithms, Combinatorics and Optimization

School of Computer Science

Georgia Institute of Technology

Date: Wednesday, May 9th, 2018

Time:  2pm
Location: Klaus 3100

Committee:

Dr. Dana Randall (adviser) , School of Computer Science, Georgia Institute of Technology

Dr. Sebastian Pokutta, School of Industrial and Systems Engineering, Georgia Institute of Technology
Dr. Andrea Richa, School of Computing, Informatics, and Decision Systems Engineering, Arizona State University
Dr. Prasad Tetali, School of Mathematics, Georgia Institute of Technology
Dr. Eric Vigoda (reader), School of Computer Science, Georgia Institute of Technology

The thesis is available for public inspection in the School of Mathematics lounge (Skiles 236), the ARC lounge (Klaus 2222), the ISyE PhD student lounge and the URL http://aco.gatech.edu/events/final-doctoral-examination-and-defense-dissertation-sarah-cannon

Abstract:

The problem of generating random samples from large, complex sets is widespread across the sciences, where such samples provide one way to begin to learn about the sets' typical properties. However, when the samples generated are unexpectedly correlated or drawn from the wrong distribution, this can produce misleading conclusions. One way to generate random samples is with Markov chains, which are widely used but often applied  without careful analysis of their mixing time, how long they must run for until they are guaranteed to produce good samples. We present new mixing time bounds for two sampling problems from discrete geometry: dyadic tilings, combinatorial structures with applications in machine learning and harmonic analysis, and 3-colorings on a grid, an instance of the celebrated  antiferromagnetic Potts model from statistical physics.  Both of these results required the development of new techniques. 

In addition, we use Markov chains in a novel way to address research questions in programmable matter. Here, a main goal is to understand how simple computational elements can collectively accomplish complicated system-level goals. In an abstracted setting, we show that groups of particles executing our simple processes, based on Markov chains, can accomplish various tasks. This includes compression, a behavior exhibited by natural distributed systems such as fire ants and honey bees, and shortcut bridging, where the particles build bridges that optimize the same global trade-off as certain bridge-building ant colonies. 

Throughout, a key ingredient is the interplay between global properties of Markov chains, including but not limited to mixing time, and their dependence on local moves, or Markov chain transitions that change only a small part of the configuration. We call the global behavior that arises out of these local moves and their probabilities emergent behavior. In addition to understanding the relationship between local moves and mixing times in order to give sampling guarantees, our work on programmable matter harnesses this interaction between local and emergent behavior in a novel way, to develop distributed algorithms.