CS Seminar: Sarah Miracle

Event Date: 
Mon, 2014-02-17 10:00 - 11:30

Sarah Miracle

School of Computer Science Georgia Tech

Monday, February 17, 2014 10:10AM-11:30AM
655 McBryde

Card Shuffling and Other Sampling Algorithms for Discrete Models from Chemistry, Economics, and Discrete Mathematics

Markov chains allow us to obtain information efficiently from exponentially large sets through random sampling. These algorithms are common across scientific and engineering disciplines, particularly statistical physics, biology, operations research, and computer science. Algorithms based on Markov chains perform a random walk on a large set of configurations. A chain is designed so that after a sufficient period of time, it will converge to a useful distribution over the whole set. Chains that converge quickly provide good tools for sampling, approximate counting and many other applications. My work applies rigorous Markov chain analysis techniques from computer science and probability to the study of applied problems and uses the application domain to inform our design and analysis of efficient sampling algorithms.
In this talk, I will discuss problems that arise in the areas of discrete mathematics, chemistry and economics. First, I will discuss the problem of sampling biased permutations, which arises in the context of self-organizing lists. Here, we show that a natural Markov chain, which has previously eluded analysis except in a few special cases, is efficient for two large classes of bias. Next, I will show a surprising connection between colloids, which are mixtures of molecules that separate, and the Schelling model, which was proposed by Nobel Price winning economist Thomas Schelling to understand the causes of racial segregation. In the study of colloids, scientists conjecture that entropic effects can cause separation at high density. Using insights from the well-studied Ising model of ferromagnetism we proved, for the first time, the existence of this entropy-driven separation for a general family of statistical physics models. We then extended these techniques to give a new rigorous underpinning to the Schelling model.

Sarah Miracle is currently a graduate student at the Georgia Institute of Technology. In 2003, she graduated from Vanderbilt University with a BE in computer engineering and mathematics and a MS in computer science. She worked as an engineer and a manager at National Instruments in Austin, TX for five years before returning to academia. In the fall of 2008, she started work on her Ph.D. in Algorithms, Combinatorics and Optimization at the Georgia Institute of Technology. Her advisor is Dr. Dana Randall and her research interests include randomized algorithms and Markov chains. She is the recipient of a Department of Energy Office of Science Graduate Fellowship and an Atlanta Achievement Rewards for College Scientists Foundation Scholar Award.