Georgia Tech’s Subhash Khot, Assistant Professor of Computing, recently won the Best Paper Award at the 45th Annual Symposium on Foundations of Computer Science (FOCS 2004), held last month in Rome, Italy. Khot was the sole author of the award-winning paper titled, "Hardness of Approximating the Shortest Vector Problem in Lattices". He submitted two other papers in this year’s FOCS as well -“Ruling out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique” and “Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs,” the latter co-authored with Guy Kindler, Elchanan Mossel and Ryan O'donnell.

Khot earned his Ph.D. in Computer Science from Princeton University in 2003 under his advisor Professor Sanjeev Arora. He stayed at Princeton for another year as a member of the Institute for Advanced Study before joining the Theory Group at Georgia Tech’s College of Computing.

FOCS is a premier theory conference, and is considered one of the most important venues for presenting new results in theoretical computer sciences. The annual FOCS conference is sponsored by the IEEE Computer Society and is organized by what is now called the IEEE Technical Committee on Mathematical Foundations of Computer Science (TC-MFCS). FOCS began in 1960 as a "Symposium on Switching Circuit Theory and Logic Design" (SCT&LD), changed its name in 1966 to the "Symposium on Switching and Automata Theory" (SWAT), and assumed its current name in 1975.

The FOCS program committee may choose up to three papers as Best Papers each year. The main criterion for giving the award is: introduction of a strong new technique, solution of a long-standing open problem, introduction and solution of an interesting and important new problem. The program committee must also have substantial confidence in the accuracy of the paper. Each author on each of the selected Best Papers receives a certificate or plaque with the name of the award, the name of the paper, and the names of the authors of the paper. The other Best Paper Award at FOCS 2004 was “Cryptography in NC^0” by authors Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz.

The Georgia Tech College of Computing houses one of the largest computer science programs in the country and provides high quality instruction that integrates computing knowledge into other academic disciplines, as well as aspects of daily life. The College of Computing is ranked 9th overall at the doctoral level, and houses several interdisciplinary research centers including the Georgia Tech Information Security Center (GTISC), the Graphics, Visualization and Usability Center (GVU), Center for Experimental Research in Computer Systems (CERCS), and the Modeling & Simulation Research and Education Center (MSREC).