{"51595":{"#nid":"51595","#data":{"type":"news","title":"ARC ThinkTank Faculty Present Theoretical Advances","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003E(December 17, 2006)\u2014\u003C\/strong\u003EMembers of the Algorithms \u0026amp; Randomness Center and ThinkTank (ARC ThinkTank) recently presented theoretical advances at IEEE sponsored Symposium on Foundations of Computer Science (FOCS) in Berkeley, CA. ARC ThinkTank brings together faculty from the College of Computing at Georgia Tech, along with Math and ISyE to find algorithms and algorithmic models for real-world problems across the sciences and, in the process, seeking new directions and techniques for the emerging theory of algorithms.\u003C\/p\u003E\n\u003Cp\u003EThe 47th annual symposium was held Oct. 22-24, and featured the following contributions from ARC ThinkTank members and College of Computing faculty:\u003C\/p\u003E\n\u003Cp\u003EAssistant Professor Yael Tauman Kalai presented a paper (joint with Ran Raz, Weizmann Institute) titled \u0022Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP,\u0022 giving a new method of non-interactive proof that seems widely applicable.\u003C\/p\u003E\n\u003Cp\u003EAssistant Professor Subhash Khot had two papers, one with Ryan O\u0027Donnell (CMU) titled \u0022SDP gaps and UGC-hardness for MaxCutGain\u0022 improving the known hardness results for the well-known maximum cut problem, and another with his graduate student Ashok Kumar Ponnuswami, Vitaly Feldman (Harvard) and College of Computing graduate Parikshit Gopalan on \u0022New Results for Learning Noisy Parities and Halfspaces,\u0022 showing, among other things, that the problem of learning a slightly noisy threshold function is surprisingly hard.\u003C\/p\u003E\n\u003Cp\u003EAssociate Professor Milena Mihail had a paper with her former student Amin Saberi (Stanford), Tomas Feder and Adam Guetz (Stanford), titled \u0022A local switch markov chain on given degree graphs with application in connectivity of peer-to-peer networks,\u0022 analyzing a random process motivated by an application to networks.\u003C\/p\u003E\n\u003Cp\u003EProfessor and ARC ThinkTank Director Santosh Vempala also had two papers, one with his student Luis Rademacher (MIT), showing a quadratic lower bound on the complexity of volume computation, \u0022Disperson of Mass and the Complexity of Randomized Geometric Algorithms;\u0022 and another with Laszlo Lovasz (Eotvos Lorand University) titled \u0022Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization,\u0022 establishing that basic problems can be solved in polynomial time for any logconcave function in high-dimensional space.\u003C\/p\u003E\n\u003Cp\u003EFor more information about the ARC ThinkTank, \u003Ca href=\u0022http:\/\/www.arc.gatech.edu\u0022 target=\u0022_blank\u0022\u003Eclick here\u003C\/a\u003E.\u003C\/p\u003E\n\u003Cp\u003EFor more information about the 47th annual FOCS symposium, \u003Ca href=\u0022http:\/\/focs06.cs.princeton.edu\/\u0022 target=\u0022_blank\u0022\u003Eclick here\u003C\/a\u003E.\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EMembers of the Algorithms \u0026amp; Randomness Center and ThinkTank\u00a0presented numerous papers at the 47th Annual Symposium on Foundations of Computer Science.\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":"","uid":"27154","created_gmt":"2010-02-09 21:46:38","changed_gmt":"2016-10-08 03:05:00","author":"Louise Russo","boilerplate_text":"","field_publication":"","field_article_url":"","dateline":{"date":"2006-12-18T00:00:00-05:00","iso_date":"2006-12-18T00:00:00-05:00","tz":"America\/New_York"},"extras":[],"groups":[{"id":"47223","name":"College of Computing"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}