{"72765":{"#nid":"72765","#data":{"type":"news","title":"Computing\u0027s Vigoda Wins Renowned Fulkerson Prize","body":[{"value":"\u003Cp\u003ECollege of Computing associate professor Eric Vigoda recently won the 2006 Delbert Ray Fulkerson Prize for his paper titled \u0022A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries,\u0022 co-authored with Mark Jerrum at the University of Edinburgh and Alistair Sinclair at UC Berkeley. The \u0022Fulkerson Prize\u0022 is a prestigious award given every three years for outstanding papers in the area of Discrete Mathematics, and is sponsored jointly by the Mathematical Programming Society and the American Mathematical Society. Vigoda is the first from the College of Computing at Georgia Tech to win this celebrated prize, although past Georgia Tech winners include Arkadi Nemirovski (1982) from the School of Industrial and Systems Engineering and Robin Thomas (1994) from the School of Mathematics.\u003C\/p\u003E\n\u003Cp\u003EThe permanent of a matrix is currently a well-studied combinatorial problem with applications in many fields, as it corresponds to the number of perfect matchings of a bipartite graph. For example in physics, computing the permanent is central to the study of the Dimer and Ising Models, although the exact computation of the permanent is intractable. Mathematicians began studying the permanent about two centuries ago, partly because of its superficial similarity to the determinant, which is a much easier problem.\u003C\/p\u003E\n\u003Cp\u003EVigoda\u0027s breakthrough discovery is a randomized algorithm which approximates the permanent to within an arbitrarily close factor in time polynomial and in the size of the input. Therefore, with the use of randomness, arbitrarily good approximations can still be obtained. Vigoda\u0027s paper also introduces techniques that have already found several important computing, physics, and mathematical applications. The award was presented at the International Symposium on Mathematical Programming this month in Rio de Janeiro.\n\u003C\/p\u003E\n\u003Cp\u003EFor more information about the Fulkerson Prize, visit \u003Ca href=\u0027http:\/\/www.ams.org\/prizes\/fulkerson-prize.html\u0027\u003Ehttp:\/\/www.ams.org\/prizes\/fulkerson-prize.html\u003C\/a\u003E.\n\u003C\/p\u003E\n\u003Cp\u003ETo view Vigoda\u0027s award-winning paper, visit \u003Ca href=\u0027http:\/\/www.cc.gatech.edu\/~vigoda\/Permanent.pdf\u0027\u003Ehttp:\/\/www.cc.gatech.edu\/~vigoda\/Permanent.pdf\u003C\/a\u003E.\n\u003C\/p\u003E\n\u003Cp\u003E\u003Cstrong\u003EWriter:\u003C\/strong\u003E Joy Weaks, College of Computing\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"Eric Vigoda won the 2006 Fulkerson Prize for his paper titled \u0022A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries,\u0022 co-authored with Mark Jerrum, U. of Edinburgh and Alistair Sinclair, UC Berkeley.","format":"limited_html"}],"field_summary_sentence":[{"value":"Professor recognized for discrete mathematics paper"}],"uid":"27301","created_gmt":"2006-08-16 00:00:00","changed_gmt":"2016-10-08 03:02:23","author":"Elizabeth Campell","boilerplate_text":"","field_publication":"","field_article_url":"","dateline":{"date":"2006-08-16T00:00:00-04:00","iso_date":"2006-08-16T00:00:00-04:00","tz":"America\/New_York"},"extras":[],"hg_media":{"72766":{"id":"72766","type":"image","title":"Eric Vigoda","body":null,"created":"1449177954","gmt_created":"2015-12-03 21:25:54","changed":"1475894663","gmt_changed":"2016-10-08 02:44:23"}},"media_ids":["72766"],"related_links":[{"url":"http:\/\/www-static.cc.gatech.edu\/~vigoda\/","title":"Vigoda\\\u0027s Faculty Page"},{"url":"http:\/\/www.ams.org\/prizes\/fulkerson-prize.html","title":"Fulkerson Prize"},{"url":"http:\/\/www.cc.gatech.edu\/~vigoda\/Permanent.pdf","title":"Vigoda"}],"groups":[{"id":"1214","name":"News Room"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cstrong\u003ELisa Grovenstein\u003C\/strong\u003E\u003Cbr \/\u003ECommunications \u0026amp; Marketing\u003Cbr \/\u003E\u003Ca href=\u0022http:\/\/www.gatech.edu\/contact\/index.html?id=lgrovenste3\u0022\u003EContact Lisa Grovenstein\u003C\/a\u003E\u003Cbr \/\u003E\u003Cstrong\u003E404-894-8835\u003C\/strong\u003E","format":"limited_html"}],"email":["lisa.grovenstein@comm.gatech.edu"],"slides":[],"orientation":[],"userdata":""}}}