{"555441":{"#nid":"555441","#data":{"type":"event","title":"PhD Defense by Prateek Bhakta","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle: Markov Chains for Weighted Lattice Structures\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EPrateek Bhakta\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EAlgorithms, Combinatorics and Optimization Ph.D. Candidate\u003C\/p\u003E\u003Cp\u003ESchool of Computer Science\u003C\/p\u003E\u003Cp\u003ECollege of Computing\u003C\/p\u003E\u003Cp\u003EGeorgia Institute of Technology\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003EDate: Tuesday, July 25th, 2016\u003C\/p\u003E\u003Cp\u003ETime: 12:00pm\u003C\/p\u003E\u003Cp\u003ELocation: Klaus 2100\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ECommittee\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E-------------\u003C\/p\u003E\u003Cp\u003EProf. Dana Randall, School of Computer Science (Advisor)\u003C\/p\u003E\u003Cp\u003EProf. Eric Vigoda, School of Computer Science\u003C\/p\u003E\u003Cp\u003EProf. Milena Mihail, School of Computer Science\u003C\/p\u003E\u003Cp\u003EProf. Prasad Tetali, School of Mathematics and School of Computer Science\u003C\/p\u003E\u003Cp\u003EProf. David Goldberg, School of Industrial Systems and Engineering\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003E--------------\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EMarkov chains are an essential tool for sampling from large sets, and are ubiquitous across many scientific fields, including statistical physics, industrial engineering, and computer science. To be a useful tool for sampling, the number of steps needed for a Markov chain to converge approximately to the target probability distribution, also known as the mixing time, should be a small polynomial in n, the size of a state.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003EWe study problems that arise from the design and analysis of Markov chains that sample from configurations of lattice structures. Specifically, we will be interested in settings where each state is sampled with a non-uniform weight that depends on the structure of the configuration. These weighted lattice models arise naturally in many contexts, and are typically more difficult to analyze than their unweighted counterparts. Our focus will be on exploiting these weightings both to develop new efficient algorithms for sampling and to prove new mixing time bounds for existing Markov chains.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003EFirst, we will present an efficient algorithm for sampling fixed rank elements from a graded poset, which includes sampling integer partitions of n as a special case. Then, we study the problem of sampling weighted perfect matchings on lattices using a natural Markov chain based on \u0022rotations\u0022, and provide evidence towards understanding why this Markov chain has empirically been observed to converge slowly. Finally, we present and analyze a generalized version of the Schelling Segregation model, first proposed in 1971 by economist Thomas Schelling to explain possible causes of racial segregation in cities. We identify conditions under which segregation, or clustering, is likely or unlikely to occur. \u0026nbsp;Our analysis techniques for all three problems are drawn from the interface of theoretical computer science with discrete mathematics and statistical physics.\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E \u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Markov Chains for Weighted Lattice Structures"}],"uid":"27707","created_gmt":"2016-07-26 09:58:52","changed_gmt":"2016-10-08 02:18:25","author":"Tatianna Richardson","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2016-07-25T13:00:00-04:00","event_time_end":"2016-07-25T15:00:00-04:00","event_time_end_last":"2016-07-25T15:00:00-04:00","gmt_time_start":"2016-07-25 17:00:00","gmt_time_end":"2016-07-25 19:00:00","gmt_time_end_last":"2016-07-25 19: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":"78771","name":"Public"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}