{"590609":{"#nid":"590609","#data":{"type":"event","title":"PhD Defense by Ben Cousins","body":[{"value":"\u003Cp\u003ETitle: Efficient High-dimensional Sampling and Integration\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nBen Cousins\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022http:\/\/www.cc.gatech.edu\/~bcousins\/\u0022 target=\u0022_blank\u0022\u003Ehttp:\/\/www.cc.gatech.edu\/~bcousins\/\u003C\/a\u003E\u003C\/p\u003E\r\n\r\n\u003Cp\u003EPh.D. Candidate in Algorithms, Combinatorics, and Optimization\u003C\/p\u003E\r\n\r\n\u003Cp\u003ESchool of Computer Science\u003C\/p\u003E\r\n\r\n\u003Cp\u003ECollege of Computing\u003C\/p\u003E\r\n\r\n\u003Cp\u003EGeorgia Institute of Technology\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u003Ca href=\u0022mailto:bcousins3@gatech.edu\u0022\u003Ebcousins3@gatech.edu\u003C\/a\u003E\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nDate:\u0026nbsp;Friday, April 28, 2017\u003Cbr \/\u003E\r\nTime: 10:30 AM\u003Cbr \/\u003E\r\nLocation: Klaus 2100\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nCommittee:\u003Cbr \/\u003E\r\nDr. Santosh Vempala, School of Computer Science (Advisor)\u003Cbr \/\u003E\r\nDr. Ton Dieker, Department of Industrial Engineering and Operations\u003Cbr \/\u003E\r\nResearch, Columbia University\u003Cbr \/\u003E\r\nDr. Dana Randall, School of Computer Science\u003Cbr \/\u003E\r\nDr. Prasad Tetali, School of Mathematics\u003Cbr \/\u003E\r\nDr. Eric Vigoda, School of Computer Science\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nAbstract:\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EHigh-dimensional sampling and integration is a shining example of\u003Cbr \/\u003E\r\nthe power of randomness in computation, where randomness provably helps.\u003Cbr \/\u003E\r\nAdditionally, the theoretical advances for these problems seem to lead to\u003Cbr \/\u003E\r\nefficient algorithms in practice. The algorithms and techniques extend to a\u003Cbr \/\u003E\r\nvariety of fields, such as operations research and systems biology.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nThe main contribution is an O*(n^3) randomized algorithm for estimating the\u003Cbr \/\u003E\r\nvolume of a well-rounded convex body, improving on the previous best\u003Cbr \/\u003E\r\ncomplexity of O*(n^4). Previously, the known approach for potentially\u003Cbr \/\u003E\r\nachieving such complexity relied on a positive resolution of the KLS\u003Cbr \/\u003E\r\nhyperplane conjecture, a central open problem in convex geometry. Building\u003Cbr \/\u003E\r\nto this result, algorithmic improvements for Gaussian sampling and\u003Cbr \/\u003E\r\nintegration are developed. A crucial algorithmic ingredient is analyzing an\u003Cbr \/\u003E\r\naccelerated cooling schedule with Gaussians that achieves a perfect\u003Cbr \/\u003E\r\ntrade-off with the complexity of Gaussian sampling.\u003Cbr \/\u003E\r\n\u003Cbr \/\u003E\r\nThe theoretical insights transfer over to efficient algorithms in practice,\u003Cbr \/\u003E\r\nas is demonstrated by a MATLAB adaptation of the volume algorithm. The\u003Cbr \/\u003E\r\nperformance vastly exceeds the current best deterministic algorithms.\u003Cbr \/\u003E\r\nAdditionally, an implementation of the sampling algorithm, when applied to\u003Cbr \/\u003E\r\nsystems biology for the analysis of metabolic networks, significantly\u003Cbr \/\u003E\r\nadvances the frontier of computational feasibility.\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"Efficient High-dimensional Sampling and Integration"}],"uid":"27707","created_gmt":"2017-04-19 13:28:48","changed_gmt":"2017-04-19 13:28:48","author":"Tatianna Richardson","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2017-04-28T11:30:00-04:00","event_time_end":"2017-04-28T13:30:00-04:00","event_time_end_last":"2017-04-28T13:30:00-04:00","gmt_time_start":"2017-04-28 15:30:00","gmt_time_end":"2017-04-28 17:30:00","gmt_time_end_last":"2017-04-28 17:30: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":"78751","name":"Undergraduate students"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}