{"609441":{"#nid":"609441","#data":{"type":"event","title":"PhD Defense by David Dufree","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle\u003C\/strong\u003E:\u0026nbsp; Algorithmic Manipulation of Probability Distributions for\u003Cbr \/\u003E\r\nNetworks and Mechanisms\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDavid Durfee\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\u003E\u003Cstrong\u003EDate\u003C\/strong\u003E: Wednesday, Aug 22, 2018\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ETime\u003C\/strong\u003E: 10am (EST)\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ELocation\u003C\/strong\u003E: Klaus 2100\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003ECommittee\u003C\/strong\u003E:\u003C\/p\u003E\r\n\r\n\u003Cp\u003E--------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Richard Peng (Advisor), School of Computer Science, Georgia Institute of Technology\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Santosh Vempala, School of Computer Science, Georgia Institute of Technology\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Xi Chen, Department of Computer Science, Columbia University\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Eric Vigoda, School of Computer Science, Georgia Institute of Technology\u003C\/p\u003E\r\n\r\n\u003Cp\u003EDr. Alejandro Toriello, School of Industrial and Systems Engineering,\u003Cbr \/\u003E\r\nGeorgia Institute of Technology\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E:\u003C\/p\u003E\r\n\r\n\u003Cp\u003E--------------\u003C\/p\u003E\r\n\r\n\u003Cp\u003EIn this thesis we present four different works that solve problems in\u003Cbr \/\u003E\r\ndynamic graph algorithms, spectral graph algorithms, computational\u003Cbr \/\u003E\r\neconomics, and differential privacy. While these areas are not all\u003Cbr \/\u003E\r\nstrongly correlated, there were similar techniques integral to each of\u003Cbr \/\u003E\r\nthe results. In particular, a key to each result was carefully\u003Cbr \/\u003E\r\nconstructing probability distributions that interact with fast\u003Cbr \/\u003E\r\nalgorithms on networks or mechanisms for economic games and private data\u003Cbr \/\u003E\r\noutput. For the fast algorithms on networks this required utilizing\u003Cbr \/\u003E\r\nessential graph properties for each network to determine sampling\u003Cbr \/\u003E\r\nprobabilities for sparsification procedures that we often recursively\u003Cbr \/\u003E\r\napplied to achieve runtime speedups. For mechanisms in economic games we\u003Cbr \/\u003E\r\nconstruct a gadget game mechanism by carefully manipulating the expected\u003Cbr \/\u003E\r\npayoff resulting from the probability distribution on the strategy space\u003Cbr \/\u003E\r\nto give a correspondence between two economic games and imply a hardness\u003Cbr \/\u003E\r\nequivalence. For mechanisms on private data output we construct a\u003Cbr \/\u003E\r\nsmoothing framework for input data that allows private output from known\u003Cbr \/\u003E\r\nmechanisms while still maintaining certain levels of accuracy.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Algorithmic Manipulation of Probability Distributions for Networks and Mechanisms"}],"uid":"27707","created_gmt":"2018-08-08 14:36:08","changed_gmt":"2018-08-08 14:36:08","author":"Tatianna Richardson","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2018-08-22T11:00:00-04:00","event_time_end":"2018-08-22T13:01:00-04:00","event_time_end_last":"2018-08-22T13:01:00-04:00","gmt_time_start":"2018-08-22 15:00:00","gmt_time_end":"2018-08-22 17:01:00","gmt_time_end_last":"2018-08-22 17:01: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":""}}}