(December 17, 2006)--Members of the Algorithms & 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.

The 47th annual symposium was held Oct. 22-24, and featured the following contributions from ARC ThinkTank members and College of Computing faculty:

Assistant Professor Yael Tauman Kalai presented a paper (joint with Ran Raz, Weizmann Institute) titled "Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP," giving a new method of non-interactive proof that seems widely applicable.

Assistant Professor Subhash Khot had two papers, one with Ryan O'Donnell (CMU) titled "SDP gaps and UGC-hardness for MaxCutGain" 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 "New Results for Learning Noisy Parities and Halfspaces," showing, among other things, that the problem of learning a slightly noisy threshold function is surprisingly hard.

Associate Professor Milena Mihail had a paper with her former student Amin Saberi (Stanford), Tomas Feder and Adam Guetz (Stanford), titled "A local switch markov chain on given degree graphs with application in connectivity of peer-to-peer networks," analyzing a random process motivated by an application to networks.

Professor 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, "Disperson of Mass and the Complexity of Randomized Geometric Algorithms;" and another with Laszlo Lovasz (Eotvos Lorand University) titled "Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization," establishing that basic problems can be solved in polynomial time for any logconcave function in high-dimensional space.

For more information about the ARC ThinkTank, click here.

For more information about the 47th annual FOCS symposium, click here.