{"605482":{"#nid":"605482","#data":{"type":"event","title":"Phd Defense by Sarah Cannon","body":[{"value":"\u003Cp\u003ETitle: Markov Chains and Emergent Behavior for Problems from Discrete\u0026nbsp;Geometry\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003ESarah Cannon\u003C\/p\u003E\r\n\r\n\u003Cp\u003EAlgorithms, Combinatorics and Optimization\u003C\/p\u003E\r\n\r\n\u003Cp\u003ESchool of Computer Science\u003C\/p\u003E\r\n\r\n\u003Cp\u003EGeorgia Institute of Technology\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDate:\u0026nbsp;Wednesday, May 9th, 2018\u003C\/p\u003E\r\n\r\n\u003Cp\u003ETime: \u0026nbsp;2pm\u003Cbr \/\u003E\r\nLocation: Klaus 3100\u003C\/p\u003E\r\n\r\n\u003Cp\u003ECommittee:\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Dana Randall (adviser)\u0026nbsp;, School of Computer Science, Georgia Institute of Technology\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Sebastian Pokutta,\u0026nbsp;School of Industrial and Systems Engineering,\u0026nbsp;Georgia Institute of Technology\u003Cbr \/\u003E\r\nDr. Andrea Richa,\u0026nbsp;School of Computing, Informatics, and Decision Systems Engineering, Arizona State University\u003Cbr \/\u003E\r\nDr. Prasad Tetali, School of Mathematics,\u0026nbsp;Georgia Institute of Technology\u003Cbr \/\u003E\r\nDr. Eric Vigoda (reader), School of Computer Science,\u0026nbsp;Georgia Institute of Technology\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cbr \/\u003E\r\nThe thesis is available for public inspection in the School of\u0026nbsp;Mathematics lounge (Skiles 236), the ARC lounge (Klaus 2222), the ISyE\u0026nbsp;PhD student lounge and the URL\u0026nbsp;\u003Ca href=\u0022http:\/\/aco.gatech.edu\/events\/final-doctoral-examination-and-defense-dissertation-sarah-cannon\u0022 id=\u0022LPlnk794615\u0022 target=\u0022_blank\u0022\u003Ehttp:\/\/aco.gatech.edu\/events\/final-doctoral-examination-and-defense-dissertation-sarah-cannon\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003EAbstract:\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThe 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\u0026#39; typical properties.\u0026nbsp;However, when the samples generated are unexpectedly correlated or drawn from the wrong distribution, this can produce misleading conclusions.\u0026nbsp;One way to generate random samples is with\u0026nbsp;\u003Cem\u003EMarkov chains\u003C\/em\u003E,\u0026nbsp;which are widely used but often applied\u0026nbsp;\u0026nbsp;without careful analysis of their\u0026nbsp;\u003Cem\u003Emixing time\u003C\/em\u003E, how long they must run for until they are guaranteed to produce good samples.\u0026nbsp;We present new mixing time bounds for two sampling problems from discrete geometry:\u0026nbsp;\u003Cem\u003Edyadic tilings\u003C\/em\u003E, combinatorial structures with applications in machine learning and harmonic analysis, and\u0026nbsp;\u003Cem\u003E3-colorings\u003C\/em\u003E\u0026nbsp;on a grid, an instance of the celebrated\u0026nbsp; antiferromagnetic Potts model from statistical physics.\u0026nbsp; Both of these results required the development of new techniques.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn addition, we\u0026nbsp;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\u0026nbsp;\u003Cem\u003Ecompression\u003C\/em\u003E, a behavior exhibited by natural distributed systems such as fire ants and honey bees, and\u0026nbsp;\u003Cem\u003Eshortcut bridging\u003C\/em\u003E, where the particles build bridges that optimize the same global trade-off as certain bridge-building\u0026nbsp;ant\u0026nbsp;colonies.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThroughout, a key ingredient is the interplay between global properties of Markov\u0026nbsp;chains, including but not limited to mixing time, and their dependence on\u003Cem\u003E\u0026nbsp;local move\u003C\/em\u003Es,\u0026nbsp;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\u0026nbsp;\u003Cem\u003Eemergent behavior\u003C\/em\u003E. In addition to understanding the relationship between local moves and mixing times in order to give sampling guarantees, our work on programmable matter harnesses\u0026nbsp;this interaction between local and emergent behavior in a novel way, to develop distributed\u0026nbsp;algorithms.\u0026nbsp;\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Markov Chains and Emergent Behavior for Problems from Discrete Geometry"}],"uid":"27707","created_gmt":"2018-04-24 19:58:26","changed_gmt":"2018-04-24 19:58:26","author":"Tatianna Richardson","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-05-09T15:00:00-04:00","event_time_end":"2018-05-09T17:00:00-04:00","event_time_end_last":"2018-05-09T17:00:00-04:00","gmt_time_start":"2018-05-09 19:00:00","gmt_time_end":"2018-05-09 21:00:00","gmt_time_end_last":"2018-05-09 21:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"221981","name":"Graduate Studies"}],"categories":[],"keywords":[{"id":"100811","name":"Phd Defense"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1788","name":"Other\/Miscellaneous"}],"invited_audience":[{"id":"78761","name":"Faculty\/Staff"},{"id":"78771","name":"Public"},{"id":"174045","name":"Graduate students"},{"id":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}