ARC ThinkTank Makes Strong Contribution at Top ACM Symposium

July 19, 2007

(July 20, 2007) - Five papers from members of the Algorithms and Randomness Center and ThinkTank (ARC ThinkTank) were presented at the Symposium on the Theory of Computing (STOC 2007), June 10-13 in San Diego, California. The symposium is sponsored by the Association for Computing Machinery (ACM) Special Interest Group on Algorithms and Computation Theory (SIGACT) and is one of the top annual conferences in theoretical computer science.

ARC ThinkTank brings together faculty from the College of Computing at Georgia Tech, along with the Schools of Math and Industrial Systems and Engineering (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 following papers were presented and and can be downloaded by ACM subscribers:

"Playing Games with Approximation Algorithms" - co-authored by Adam Kalai, assistant professor

"Combinatorial Complexity in O-minimal Geometry" - by Saugata Basu, associate professor joint with the School of Mathematics

"Randomly Coloring Planar Graphs with Fewer Colors than the Maximum Degree" - co-authored by Eric Vigoda, associate professor and Juan Vera, post-doc

"Eisenberg-Gale Markets: Algorithms and Structural Properties" - co-authored by Vijay Vazirani, professor and former student Kamal Jain, Microsoft Research

"Simple Deterministic Approximation Algorithms for Counting Matchings" - co-authored by Prasad Tetali, professor joint with the School of Mathematics

The ARC ThinkTank brings together faculty from the College of Computing at Georgia Tech, along with the Schools of Math and Industrial Systems and Engineering (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.

More information on STOC '07 can be found at the symposium website.