{"604802":{"#nid":"604802","#data":{"type":"news","title":"Computer Scientists Make KLS Conjecture Breakthrough","body":[{"value":"\u003Cp\u003EThe\u0026nbsp;KLS\u0026nbsp;conjecture posits one of the classic\u0026nbsp;mathematical questions: given a shape and told to cut it into two equal halves, what is the minimum possible surface area needed to create those halves?\u003C\/p\u003E\r\n\r\n\u003Cp\u003ESchool of Computer Science Professor\u0026nbsp;\u003Cstrong\u003E\u003Ca href=\u0022https:\/\/www.scs.gatech.edu\/people\/11074\/santosh-vempalas\u0022\u003ESantosh\u0026nbsp;Vempala\u003C\/a\u003E\u003C\/strong\u003E\u0026nbsp;and University of Washington Assistant Professor\u0026nbsp;\u003Cstrong\u003E\u003Ca href=\u0022http:\/\/yintat.com\/\u0022\u003EYin Tat Lee\u003C\/a\u003E\u003C\/strong\u003E\u0026nbsp;recently discovered a breakthrough theorem that makes progress toward\u0026nbsp;the\u0026nbsp;KLS\u0026nbsp;conjecture.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EAccording to the\u0026nbsp;KLS\u0026nbsp;conjecture, the best way to cut the shape is to use a hyperplane up to a constant factor. A hyperplane is a straight-line cut in higher dimensions, a slice essentially. As long as the shape is convex, meaning every point can see every other point, it will be an effective cut. The surface area may not be the least, but it will be within a small factor of the best possible.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026ldquo;The fact that a hyperplane is nearly optimal\u0026nbsp;doesn\u0026rsquo;t change as the dimension goes up,\u0026rdquo;\u0026nbsp;Vempala\u0026nbsp;said.\u003C\/p\u003E\r\n\r\n\u003Ch3\u003E\u003Cstrong\u003ESearching for a constant\u003C\/strong\u003E\u003C\/h3\u003E\r\n\r\n\u003Cp\u003ESince the breakthrough In December 2016, published in a paper of their findings,\u0026nbsp;\u003Cem\u003E\u003Ca href=\u0022https:\/\/arxiv.org\/abs\/1612.01507\u0022\u003EEldan\u0026#39;s\u0026nbsp;Stochastic Localization and the\u0026nbsp;KLS\u0026nbsp;Hyperplane Conjecture: An Improved Lower Bound for Expansion\u003C\/a\u003E\u0026nbsp;\u003C\/em\u003Ethey have been asked to share their findings with mathematician s from across the country. Among these were presentations at the\u0026nbsp;\u003Ca href=\u0022http:\/\/www.msri.org\/web\/cms\u0022 target=\u0022_blank\u0022\u003EMathematical Sciences Research Institute\u003C\/a\u003E, the\u0026nbsp;\u003Ca href=\u0022https:\/\/www.math.gatech.edu\/seminars-colloquia\/series\/school-mathematics-colloquium\/santosh-vempala-20180308\u0022\u003ESchool of Mathematics Colloquium\u003C\/a\u003E\u0026nbsp;at Georgia Tech, and\u0026nbsp;\u003Ca href=\u0022http:\/\/www.math.harvard.edu\/cdm\/\u0022\u003ECurrent Developments in Mathematics\u003C\/a\u003E\u0026nbsp;\u0026ndash; a joint annual conference organized by Harvard and MIT that highlights some of the biggest mathematical discoveries of the year where\u0026nbsp;Vempala\u0026nbsp;was the only computer scientist invited to present.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026ldquo;Computer science has come of the age when its findings are of interest for their mathematics depth alone,\u0026rdquo;\u0026nbsp;Vempala\u0026nbsp;said. The KLS\u0026nbsp;conjecture was first\u0026nbsp;posited\u0026nbsp;in 1995 by\u0026nbsp;\u003Cstrong\u003ERavindran\u0026nbsp;Kannan\u003C\/strong\u003E,\u0026nbsp;\u003Cstrong\u003EL\u0026aacute;szl\u0026oacute;\u0026nbsp;Lov\u0026aacute;sz,\u003C\/strong\u003E\u0026nbsp;and\u0026nbsp;\u003Cstrong\u003EMikl\u0026oacute;s\u0026nbsp;Simonovits\u003C\/strong\u003E, whom it was named after. Since then, mathematicians have been trying to find what this constant is.\u0026nbsp;Vempala\u0026nbsp;and Lee proved the surface area could be no worse than the dimension to the power of a quarter \u0026mdash; even as the dimension increases.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026ldquo;During the last few decades, the\u0026nbsp;KLS\u0026nbsp;conjecture has been studied for many special cases and is becoming perhaps\u0026nbsp;the most fundamental questions in\u0026nbsp;high-dimensional geometry,\u0026rdquo; Lee said. \u0026ldquo;Given the importance of convexity in both mathematics and computer science in general,\u0026nbsp; and given how natural is the\u0026nbsp;statement of\u0026nbsp;KLS\u0026nbsp;conjecture, we believe both our result and our techniques will be significant to not just theoretical\u0026nbsp;computer science but many fields across subjects.\u0026rdquo;\u003C\/p\u003E\r\n\r\n\u003Ch3\u003E\u003Cstrong\u003EMaking progress on the conjecture\u003C\/strong\u003E\u003C\/h3\u003E\r\n\r\n\u003Cp\u003ETheir discovery improves on the best known bound for the constant, and as a consequence improves on the complexity of sampling and on the bounds for several other parameters in the field of convex geometry, and establishes tight bounds for others.\u003C\/p\u003E\r\n\r\n\u003Cp\u003EKannan \u0026ndash; the\u0026nbsp;K in\u0026nbsp;KLS \u0026ndash; currently a principal researcher at Microsoft Research India and distinguished visiting scientist at the Simons Institute Berkeley, notes this result makes considerable progress on the conjecture.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026quot;Lee and\u0026nbsp;Vempala\u0026rsquo;s\u0026nbsp;result on the\u0026nbsp;KLS\u0026nbsp;conjecture is an important milestone,\u0026rdquo;\u0026nbsp;Kannan\u0026nbsp;said. \u0026ldquo;They use a fundamental scheme of \u0026#39;Gaussian cooling\u0026rsquo; (to transform any distribution into a Gaussian or vice versa)\u0026nbsp;developed in earlier work of\u0026nbsp;Santosh\u0026rsquo;s to gradually reduce the problem to the simple Gaussian case.\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026ldquo;They give a beautiful proof that this reduction does not degrade the \u0026#39;isoperimetric\u0026nbsp;constant,\u0026rsquo; which is central to the conjecture. The combination of mathematical and algorithmic techniques is very impressive.\u0026quot;\u003C\/p\u003E\r\n\r\n\u003Ch3\u003E\u003Cstrong\u003EBridging math and computer science\u003C\/strong\u003E\u003C\/h3\u003E\r\n\r\n\u003Cp\u003EMathematicians have stated that the result is just one of the breakthroughs. \u0026ldquo;What is even more important than the result itself is the method of proof,\u0026rdquo; said\u0026nbsp;\u003Cstrong\u003EMark\u0026nbsp;Rudelson\u003C\/strong\u003E, a mathematics professor at the University of Michigan. \u0026ldquo;This new localization method may have applications going far beyond the original problem it was created for.\u0026rdquo;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EThey also recognize that this discovery bridges mathematics and computer science and will have\u0026nbsp;impact\u0026nbsp;for years to come. \u0026ldquo;This conjecture is important in both pure mathematics and theoretical computer science, and the remarkable work of Lee and\u0026nbsp;Vempala\u0026nbsp;exemplifies the deep synergy between these two fields,\u0026quot; said\u0026nbsp;\u003Cstrong\u003EAssaf\u0026nbsp;Naor\u003C\/strong\u003E, a professor at Princeton\u0026rsquo;s Department of Mathematics.\u0026nbsp;\u003C\/p\u003E\r\n\r\n\u003Cp\u003E\u0026ldquo;By building on insights of\u0026nbsp;Eldan, they improved the previously best-known (and hard-fought) bound in the\u0026nbsp;KLS\u0026nbsp;conjecture, obtained better algorithms, and elucidated a powerful method which they have continued to use elsewhere and will undoubtedly be a fundamental tool in future investigations.\u0026rdquo;\u003C\/p\u003E\r\n\r\n\u003Cp\u003EVempala\u0026nbsp;and Lee are researching how the conjecture relates to manifold (curved) spaces. This has led to a faster method for sampling and computing volumes of\u0026nbsp;polytopes\u0026nbsp;(geometric shapes with flat sides) in high dimension.\u0026nbsp;Vempala\u0026nbsp;will present the team\u0026#39;s findings at UC Berkeley, Stanford University, and at the\u0026nbsp;\u003Ca href=\u0022https:\/\/www.renyi.hu\/conferences\/ll70\/\u0022\u003EBuilding Bridges II\u003C\/a\u003E\u0026nbsp;conference in Budapest in July.\u0026nbsp;\u003C\/p\u003E\r\n","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"SCS\u0027s Santosh Vempala helped make a major mathematical breakthrough in the KLS conjecture."}],"uid":"34541","created_gmt":"2018-04-06 13:22:08","changed_gmt":"2018-04-09 16:33:46","author":"Tess Malone","boilerplate_text":"","field_publication":"","field_article_url":"","dateline":{"date":"2018-04-06T00:00:00-04:00","iso_date":"2018-04-06T00:00:00-04:00","tz":"America\/New_York"},"extras":[],"hg_media":{"604804":{"id":"604804","type":"image","title":"Vempala and Lee","body":null,"created":"1523021258","gmt_created":"2018-04-06 13:27:38","changed":"1523021821","gmt_changed":"2018-04-06 13:37:01","alt":"Santosh Vempala and Yin Tat Lee","file":{"fid":"230582","name":"Lee\u0026Vempala.jpg","image_path":"\/sites\/default\/files\/images\/Lee%26Vempala.jpg","image_full_path":"http:\/\/www.tlwarc.hg.gatech.edu\/\/sites\/default\/files\/images\/Lee%26Vempala.jpg","mime":"image\/jpeg","size":90208,"path_740":"http:\/\/www.tlwarc.hg.gatech.edu\/sites\/default\/files\/styles\/740xx_scale\/public\/images\/Lee%26Vempala.jpg?itok=WlgUp1MH"}}},"media_ids":["604804"],"groups":[{"id":"47223","name":"College of Computing"},{"id":"50875","name":"School of Computer Science"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003ETess Malone, Communications Officer\u003C\/p\u003E\r\n\r\n\u003Cp\u003Etess.malone@cc.gatech.edu\u003C\/p\u003E\r\n","format":"limited_html"}],"email":["tess.malone@cc.gatech.edu"],"slides":[],"orientation":[],"userdata":""}}}